.
2014-2015学年第一学期学号1208210146
《数据结构》
课程设计报告
题目：链表结构的相关函数库的设计
专业：计算机科学与技术
班级：12级计科（3）班
姓名：
指导教师：
成绩：
计算机与信息工程系
2014 年 12月 15 日
目录
1 问题分析和任务定义 (1)
1.1 任务定义 (1)
1.2 面临的问题，进行分析解决，模块之间的联系。 (1)
2概要设计和数据结构的选择 (2)
2.1 数据结构的选择 (2)
2.2 结构图 (2)
2.3 函数实现的具体算法举例 (3)
3 课程设计思路 (6)
3.1 设计函数库 (6)
4 测试结果及其分析 (7)
4.1 初始化 (7)
4.2 逆序输入元素 (8)
4.3 单链表的长度 (8)
4.4 遍历输出单链表 (8)
4.5检索查找 (9)
4.6输入插入元素的值和位置 (9)
4.7删除元素 (10)
5 小结 (10)
参考文献 (10)
附录：程序源代码 (11)
1 问题分析和任务定义
1.1 任务定义
设计出链表结构的相关函数库，以便在程序设计中调用。进行链表中元素的输入、查找、插入、删除等操作的课程设计。
要求：
（1）所设计的数据结构应尽可能节省存储空间。（2）程序的运行时间应尽可能少。
从题目看出所设计的程序应能达到的功能，设计好的程序要满足以上两点。在数据输入方面可以根据链表的特点即存储空间的连续，从创建链表到插入，删除，查找元素以及输出一系列的步骤，连贯而下。算法的实现依赖于所采用的存储结构，所以选择什么样的存储方式在课程设计中尤为重要，这也是本程序好坏的一个评定。
1.2 面临的问题，进行分析解决，模块之间的联系。
（1）在内存中开辟一块连续的内存空间，进行分析解决
（2）利用物理位置的相邻来表示变量，达到预期效果，很好的完成任务。查找元素以及输出一系列的步骤，连贯而下。
（3）使用链表的数据结构来满足尽可能节省存储空间的要求，达到要求，从创建链表到插入，删除，查找元素以及输出一系列的步骤，连贯而下。
（4）输出界面设计与各个模块的联系，设计出链表结构的相关函数库，以便在程序设计中调用，进行链表中元素的分析。
2概要设计和数据结构的选择
2.1 数据结构的选择
本程序选择的数据结构是线性表中的链式结构（单链表），原因如下：
单链表的定义：
（1）单链表是线性表的链接存储表示。其各个数据元素可以相继存储，也可以不相继存储，不过它为每个数据元素附加了一个链接指针，并形成的一个结点。
（2） 单链表的每一个结点分为两个部分：data 和link 。
（3） 链表的第一个结点的地址可以通过链表的头指针first 找到，其他结点的地址则在前趋结点的link 域中，链表的最后一个结点没有后继，在结点的link 域中放一个空指针NULL 。
（4）头指针first 为空的单链表为空表，该链表一个结点也没有，相对地，头指针first 不为空且首元结点存在的单链表为非空表，表中至少有一个结点。
2.2 结构图
图 1 结构图
创建单链表输入数据
插入数据
删除数据 查找数据
输出数据 计算表长
2.3 函数实现的具体算法举例
（1）插入函数
/* 在带头结点的单链线性表L中第i个位置之前插入元素e */
int Insert_List(LinkList L,int i,ElemType e)
{
int j=0;
LinkList p=L,s;
while(p&&j { p=p->next; j++; } if(!p||j>i-1) return ERROR; s=(LinkList)malloc(sizeof(struct LNode)); s->data=e; s->next=p->next; p->next=s; return OK; } （2）删除函数 int Delete_List(LinkList L,int i,ElemType *e) /* 在带头结点的单链线性表L中，删除第i个元素,并由e返回其值 */ { int j=0; LinkList p=L,q; while(p->next&&j p=p->next; j++; } if(!p->next||j>i-1) return 0; q=p->next; p->next=q->next; *e=q->data; free(q); return 1; } （3）查找元素 /* 当按位置查找元素，第i个元素存在时,其值赋给e并返回1,否则返回0 */ int GetElem_List(LinkList L,int i,ElemType *e) { int j=0; LinkList p=L; while(p&&j { p=p->next; j++; } if(!p||j>i) { printf("链表不存在或参数i错"); return 0; } *e=p->data; /* 取第i个元素 */ return 1; （5）显示单链表 int Disp_List(LinkList L)/*显示单链表*/ { LinkList p=L->next; if(p==Null) printf("单链表为空表"); else {printf("输出单链表:\n"); while(p!=Null) {printf("%d",p->data); printf("->"); p=p->next; } } printf("\n"); return 1; } （6）求单链表表长 int Length_List(LinkList L) { int i=0; LinkList p=L->next; while(p) { i++; p=p->next; } return i; 3 课程设计思路 一般的说，其过程如下： A. 分析链表特点 B. 分析链表功能以及操作 C. 设计函数库 D. 制定调试计划:初步调试计划 E. 编写主函数，方便后面的测试 F. 制定完整的程序测试计划 G. 书写文档，系统说明 H. 复查和审核：从技术的角度审查，从管理的角度审查 3.1 设计函数库 设计函数库不能随心所欲，想编写什么函数就编写什么函数，而是要根据分析链表所得结果，从分析结果入手，由分析我们知道链表可以进行的操作有：输入、输出、插入一个元素、删除一个元素、查找一个元素、取出一个元素。根据这些操作分别写出函数： int Insert_List(); /*插入元素*/ int Delete_List(); /*删除元素*/ int GetElem_List(); /*查找元素*/ int Disp_List(); /*显示元素*/ int Length_List(); /*求表长*/ 4 测试结果及其分析 4.1 初始化 图2 初始化 4.2 逆序输入元素 图3 逆序输入元素4.3 单链表的长度 图4 计算长度4.4 遍历输出单链表 图 5遍历 4.5检索查找 图 6查找4.6输入插入元素的值和位置 图 7插入 4.7删除元素 图 8 插入 5 小结 通过这次课设，我学会了如何把数据结构的知识应用到实践当中，同时也进一步加深了对c/c++语言语法的应用，以及深刻的掌握了数据结构和c/c++语言的结合运用。 在编程过程中，遇到了许多问题，在一次次的运行错误后，问题被一步步改正，也从中学到了许多知识。虽然我的程序还不够完善，还需加以改进以实现更多的功能，但是我会尽我最大的努力去完成它，我相信我会努力去把程序做的更加完美。 参考文献 ［1］王昆仑,李红等编著. 数据结构与算法. 北京:中国铁道出版社,2007. ［2］苏仕华等编著. 数据结构课程设计. 北京：机械工业出版社 ,2005. ［3］苏仕华编著. 数据结构与算法解析.合肥:中国科学技术大学出版社,2004. ［4］郭嵩山等著国际大学生程序设计竞赛例题解北京:电子工业出版社,2008. 附录：程序源代码 #include #include #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define Null 0 typedef int ElemType; typedef struct LNode { ElemType data; struct LNode *next; }LNode ,*LinkList; /*初始化单链表，即产生一个带头结点的空表，创建成功则返回空表的头指针*/ LinkList Init_List(void) { LinkList L; L=(LinkList) malloc(sizeof(LNode)); if(L) L->next=NULL; //产生空表，头结点的next域为空 return L; } /*按逆序产生一个长度为n链表，参数为初始化的空链表，及线性表长度n*/ /*每个元素依次插入在头结点后*/ int Create_List(LinkList L,int n) {int i; LinkList s; /*s变量用于保存新结点地址*/ printf("生成有%d个元素的线性表:\n",n); for(i=n;i>0;i--) { printf("请输入线性表中第 %d 个元素:\n",i); /*逆序输入元素*/ s=(LinkList)malloc(sizeof(LNode)); if(!s) { printf("创建结点不成功\n"); return 0; } scanf("%d",&s->data); s->next=L->next; L->next=s; } return 1; } /* 求单链表表长，返回L中数据元素个数 */ int Length_List(LinkList L) { int i=0; LinkList p=L->next; while(p) { i++; p=p->next; } return i; } /* 当按位置查找元素，第i个元素存在时,其值赋给e并返回1,否则返回0 */ int GetElem_List(LinkList L,int i,ElemType *e) { int j=0; LinkList p=L; while(p&&j { p=p->next; j++; } if(!p||j>i) { printf("链表不存在或参数i错"); return 0; } *e=p->data; /* 取第i个元素 */ return 1; } /* 按元素查找，查找链表中是否存在值为e的元素，存在，则返回L中第一个e元素的位序,若不存在,则返回值为0 */ int Locate_List(LinkList L,ElemType e) { int i=0; LinkList p=L; while(p&&p->data!=e) { p=p->next; i++; } if(p) return i; else return 0; } /* 在带头结点的单链线性表L中第i个位置之前插入元素e */ int Insert_List(LinkList L,int i,ElemType e) { int j=0; LinkList p=L,s; while(p&&j { p=p->next; j++; } if(!p||j>i-1) return ERROR; s=(LinkList)malloc(sizeof(struct LNode)); s->data=e; s->next=p->next; p->next=s; return OK; } int Delete_List(LinkList L,int i,ElemType *e) /* 在带头结点的单链线性表L中，删除第i个元素,并由e返回其值 */ { int j=0; LinkList p=L,q; while(p->next&&j { p=p->next; j++; } if(!p->next||j>i-1) return 0; q=p->next; p->next=q->next; *e=q->data; free(q); return 1; } int Disp_List(LinkList L)/*显示单链表*/ { LinkList p=L->next; if(p==Null) printf("单链表为空表"); else {printf("输出单链表:\n"); while(p!=Null) {printf("%d",p->data); printf("->"); p=p->next; } } printf("\n"); return 1; } /*显示选择提示信息函数*/ void ShowSelect() { printf("\n请选择要执行的操作：\n"); printf("-------------------------\n"); printf(" 1----初始化\n"); printf(" 2----逆序输入元素\n"); printf(" 3----求单链表长度\n"); printf(" 4----遍历输出单链表\n"); printf(" 5----在单链表中检索查找\n"); printf(" 6----向单链表中插入元素\n"); printf(" 7----从单链表中删除元素\n"); printf(" 0---- 退出\n"); printf("-------------------------\n"); printf("please input number 0~~7 \n\n"); } int main(void) {LinkList PL=NULL; int i,x,flag; int len; /*表示单链表长*/ int select; /*select变量表示用户的选择项*/ ShowSelect(); scanf("%d",&select); while(select!=0) {switch(select) {case 1: PL=Init_List(); break; case 2: printf("请输入线性表中元素个数：\n");scanf("%d",&len);Create_List(PL,len);break; case 3: len=Length_List(PL); printf("单链表表长为%d\n",len);break; case 4: Disp_List(PL);break; case 5: printf("\n请输入你想查找的数据:"); scanf("%d",&x); i= Locate_List(PL, x); if(flag) printf("该元素在顺序表中的位置是：%d\n",i) ; else printf("该元素在顺序表中不存在"); break; case 6: printf("请输入要插入的元素的值和位置，用空格分隔：\n"); scanf("%d %d",&x,&i); flag=Insert_List(PL,i,x); if(flag) printf("插入操作成功"); break; case 7: printf("请输入要删除的元素的位置：\n"); scanf("%d",&i); flag= Delete_List(PL,i,&x); if(flag) printf("删除操作成功"); break; } ShowSelect(); scanf("%d",&select); } } 数据库表结构设计参考 表名外部单位表（DeptOut） 列名数据类型（精度范围）空/非空约束条件 外部单位ID 变长字符串(50) N 主键 类型变长字符串(50) N 单位名称变长字符串(255) N 单位简称变长字符串(50) 单位全称变长字符串(255) 交换类型变长字符串(50) N 交换、市机、直送、邮局单位邮编变长字符串(6) 单位标识(英文) 变长字符串(50) 排序号整型(4) 交换号变长字符串(50) 单位领导变长字符串(50) 单位电话变长字符串(50) 所属城市变长字符串(50) 单位地址变长字符串(255) 备注变长字符串(255) 补充说明该表记录数约3000条左右，一般不做修改。初始化记录。 表名外部单位子表（DeptOutSub） 列名数据类型（精度范围）空/非空约束条件 外部子单位ID 变长字符串(50) N 父ID 变长字符串(50) N 外键 单位名称变长字符串(255) N 单位编码变长字符串(50) 补充说明该表记录数一般很少 表名内部单位表（DeptIn） 列名数据类型（精度范围）空/非空约束条件 内部单位ID 变长字符串(50) N 主键 类型变长字符串(50) N 单位名称变长字符串(255) N 单位简称变长字符串(50) 单位全称变长字符串(255) 工作职责 排序号整型(4) 单位领导变长字符串(50) 单位电话（分机）变长字符串(50) 备注变长字符串(255) 补充说明该表记录数较小（100条以内），一般不做修改。维护一次后很少修改 表名内部单位子表（DeptInSub） 列名数据类型（精度范围）空/非空约束条件内部子单位ID 变长字符串(50) N 父ID 变长字符串(50) N 外键 单位名称变长字符串(255) N 单位编码变长字符串(50) 单位类型变长字符串(50) 领导、部门 排序号Int 补充说明该表记录数一般很少 表名省、直辖市表（Province） 列名数据类型（精度范围）空/非空约束条件ID 变长字符串(50) N 名称变长字符串(50) N 外键 投递号变长字符串(255) N 补充说明该表记录数固定 表名急件电话语音记录表（TelCall） 列名数据类型（精度范围）空/非空约束条件ID 变长字符串(50) N 发送部门变长字符串(50) N 接收部门变长字符串(50) N 拨打电话号码变长字符串(50) 拨打内容变长字符串(50) 呼叫次数Int 呼叫时间Datetime 补充说明该表对应功能不完善，最后考虑此表 表名摄像头图像记录表（ScreenShot） 列名数据类型（精度范围）空/非空约束条件ID 变长字符串(50) N 拍照时间Datetime N 取件人所属部门变长字符串(50) N 取件人用户名变长字符串(50) 取件人卡号变长字符串(50) 图片文件BLOB/Image 任务： 编写一个能向表尾插入结点，并输出链表中所有数据元素的小程序 #ifndef _LINKLIST #define _LINKLIST #include } void printList_link(PLIST head ) { /*在此处完成任务，输出head为表头的单链表数据元素*/ //begin PLIST p =new NODE; p=head->next; while(p){ printf("%d ",p->data); p=p->next; } //end } void insertDataTail(PLIST head , int insData ) { /*在此处完成任务，在head为表头的单链表表尾插入数据元素insData*/ //begin PLIST p; p=head->next; while(p->next!=NULL){ p=p->next; } PLIST q = new NODE; //初始化结点 p->next=q; q->data=insData; q->next=NULL; //end } #endif 1.数据库应用系统的设计步骤 按规范设计的方法可将数据库设计分为以下六个阶段 （1）需求分析; （2）概念结构设计; （3）逻辑结构设计; （4）数据库物理设计; （5）数据库实施; （6）数据库运行和维护。 2.需求分析 需求收集和分析是数据库应用系统设计的第一阶段。明确地把它作为数据库应用系统设计的第一步是十分重要的。这一阶段收集到的基础数据和一组数据流图（Data Flow Diaˉgram———DFD）是下一步设计概念结构的基础。概念结构对整个数据库设计具有深刻影响。而要设计好概念结构，就必须在需求分析阶段用系统的观点来考虑问题、收集和分析数据及其处理。如何分析和表达用户需求呢？在众多的分析方法中，结构化分析（Structured Analysis，简称SA方法）是一个简单实用的方法。SA方法用自顶向下、逐层分解的方式分析系统。用数据流图，数据字典描述系统。然后把一个处理功能的具体内容分解为若干子功能，每个子功能继续分解，直到把系统的工作过程表达清楚为止。在处理功能逐步分解的同时，它们所用的数据也逐级分解。形成若干层次的数据流图。数据流图表达了数据和处理过程的关系。处理过程的处理逻辑常常用判定表或判定树来描述。数据字典（Data Dictionary，简称DD）则是对系统中数据的详尽描述，是各类数据属性的清单。对数据库应用系统设计来讲，数据字典是进行详细的数据收集和数据分析所获得的主要结果。数据字典是各类数据描述的集合，它通常包括以下5个部分： （1）数据项，是数据最小单位。 （2）数据结构，是若干数据项有意义的集合。 （3）数据流，可以是数据项，也可以是数据结构。表示某一处理过程的输入输出。 （4）数据存储，处理过程中存取的数据。常常是手工凭证、手工文档或计算机文件。 （5）处理过程。 数据结构的概念： 数据的逻辑结构+ 数据的存储结构+ 数据的操作； 数据的数值：=====》数据===》数值型数据整形浮点数ASCII 非数值型数据图片声音视频字符 =====》数据元素=====》基本项组成（字段，域，属性）的记录。 数据的结构： 逻辑结构 ----》线性结构（线性表，栈，队列） ----》顺序结构 ----》链式结构 ----》非线性结构(树，二叉树，图) ----》顺序结构 ----》链式结构 存储结构 -----》顺序存储 -----》链式存储 -----》索引存储 -----》哈希存储==散列存储 数据的操作： 增 删 改 查 DS ====》数据结构===》DS = (D,R); 数据结构中算法： 1、定义：有穷规则的有序集合。 2、特性： 有穷性 确定性 输入 输出 3、算法效率的衡量 时间复杂度计算===》算法中可执行依据的频度之和，记为：T(n)。 是时间的一种估计值不是准确值。 计算结果的分析：1 将最终结果的多项式中常数项去掉 2 只保留所有多项式中最高阶的项 3 最后的最高阶项要去掉其常数项 时间复杂度的量级关系： 常量阶====》对数阶===》线性阶===》线性对数阶====》平方阶===》立方阶===》指数阶 以上关系可以根据曲线图来判断算法对时间复杂度的要求 空间复杂度计算====》算法执行过程中所占用的存储空间的量级，记为：D（n）。 计算方法是在运行过程中申请的动态内存的量级计算。 ///////////////////////////////////////////////////////////////////////////////////////////////// 线性表 顺序存储====》顺序表（数组） 链式存储====》单链表 特征：对于非空表，a0是表头没有前驱。 an-1 是表尾没有后继 ai的每个元素都有一个直接前驱和直接后继 基本操作：创建表=====》增加元素====》删除元素====》改变元素值====》查询元素 1、顺序表的操作 1.1 创建顺序表=====》定义个指定类型的数组====》int a[100] ={0}; 数据库设计的基本步骤 一、数据库设计的生存期 按照规范设计的方法，考虑到数据库及其应用系统开发的全过程，将数据库 设计分为六个阶段。如下图。 ① 需求分析 需求收集和分析, 需求。 ② 概念结构设计 对需求进行综合、归纳与抽象，形成一个独立于具体 DBMS 的概念模型（用 E-R 图表示）。 ③ 逻辑结构设计 将概念结构转换为某个DBMS 所支持的数据模型（例如关系模型），并对其 进行优化。 ④ 物理结构设计 为逻辑数据模型选取一个最适合应用环境的物理结构 （包括存储结构和存取 方法）。 ⑤ 数据库实施 需求A 祈断段 T 1 概念设计阶段 i 逻辑 q 丰计阶段 1 物理. 1 殳计阶段 j 数据E L 支实施阶段 数据库运荷? 维护阶段 得到用数据字典描述的数据需求，用数据流图描述的处理 运用DBMS 提供的数据语言（例如 SQL ）及其宿主语言（例如C）,根据逻辑设计和物理设计的结果建立数据库，编制与调试应用程序，组织数据入库，并进行试运行。 ⑥数据库运行和维护 数据库应用系统经过试运行后即可投入正式运行。在数据库系统运行过程中必须不断地对其进行评价、调整与修改。 说明：设计一个完善的数据库应用系统是不可能一蹴而就的，它往往是上述 六个阶段的不断反复。 二、数据库设计阶段的内容 设计步骤既是数据库设计的过程，也包括了数据库应用系统的设计过程。下面针对各阶段的设计内容给出各阶段的设计描述。如下图。 阶段 濮块结构） 三、数据库设计阶段的模式 数据库结构设计的不同阶段形成数据库的各级模式，如下图 需求数据字睦、全系统中数据项、 分析數据證、数据存储的描述 数1E流图和判定我（利宦 闕）、数据字典中处理过程的 描述 设计 概念模型〔E?兄图） 模块设计 IPO表 编写模武装入 数JE 实施数揭库试 运行阶段 Create … L o豆恋■?. 程序编码 编译联结 测试 Tlain () * ■ A if???then ■■ i HUl 数据宇典 系窥说朋书包括： ①新系统要求、 方案和概图 ②反映新系统信息 流的数据流图 方法选择物理 存取路径建立设计 《数据结构课程设计》报告 题目：单链表操作 专业：计算机科学与技术 班级： 单链表操作 针对带头结点的单循环链表，编写实现以下操作的算法函数。 实现要求： ⑴单链表建立函数create：先输入数据到一维数组A[M]中，然后根据一维 数组A[M]建立一个单循环链表，使链表中个元素的次序与A[M]中各元素的次序相同，要求该函数的时间复杂度为O(m)； ⑵定位查找函数Locate：在所建立的单循环链表中查找并返回值为key的 第1个元素的结点指针；若找不到，则返回NULL； ⑶求出该链表中值最大和次大的元素值，要求该算法的时间复杂度为O(m)， 最大和次大的元素值通过指针变量带回，函数不需要返回值； ⑷将链表中所有值比key(值key通过形参传入)小的结点作为值为key的结 点前驱，所有值比key大的结点作为值为key的结点后继，并尽量保持原有结点之间的顺序，要求该算法的时间复杂度为O(m); ⑸设计一个菜单，具有上述处理要求和退出系统功能。 ⒈本人完成的工作： 一、定义结构体：LNode 二、编写以下函数： （1）建立单循环链表 （2）建立定位查找函数 （3）求出链表中最大和次大值 （4）将链表中的值和输入的Key比较，小的作为key前驱结点，大的作为key 的后继结点 三、设计具有上述处理要求和退出系统菜单 ⒉所采用的数据结构：单链表 数据结构的定义： typedef struct Node //定义结点的结构体 { DataType data; //数据域 struct Node *next; //指针域 }LNode; //结点的类型 ⒊所设计的函数 （1）Create(void) LNode *Create(void) //建立单循环链表，链表头结点head作为返回值{ int i,j,n,A[M]; //建立数组A【M】 LNode *head,*p,*move; head=(LNode*)malloc(sizeof(LNode)); //创建空单循环链表head->next=head; move=head; printf("请输入数组元素的个数："); //输入数组 scanf("%d",&n); printf("请输入数组："); for(i=0;i 目录 1 选题背景 (2) 2 方案与论证 (3) 2.1 链表的概念和作用 (3) 2.3 算法的设计思想 (4) 2.4 相关图例 (5) 2.4.1 单链表的结点结构 (5) 2.4.2 算法流程图 (5) 3 实验结果 (6) 3.1 链表的建立 (6) 3.2 单链表的插入 (6) 3.3 单链表的输出 (7) 3.4 查找元素 (7) 3.5 单链表的删除 (8) 3.6 显示链表中的元素个数（计数） (9) 4 结果分析 (10) 4.1 单链表的结构 (10) 4.2 单链表的操作特点 (10) 4.2.1 顺链操作技术 (10) 4.2.2 指针保留技术 (10) 4.3 链表处理中的相关技术 (10) 5 设计体会及今后的改进意见 (11) 参考文献 (12) 附录代码： (13) 1 选题背景 陈火旺院士把计算机60多年的发展成就概括为五个“一”：开辟一个新时代----信息时代，形成一个新产业----信息产业，产生一个新科学----计算机科学与技术，开创一种新的科研方法----计算方法，开辟一种新文化----计算机文化，这一概括深刻影响了计算机对社会发展所产生的广泛而深远的影响。 数据结构和算法是计算机求解问题过程的两大基石。著名的计算机科学家P.Wegner指出，“在工业革命中其核心作用的是能量，而在计算机革命中其核心作用的是信息”。计算机科学就是“一种关于信息结构转换的科学”。信息结构（数据结构）是计算机科学研究的基本课题，数据结构又是算法研究的基础。 2 方案与论证 2.1 链表的概念和作用 链表是一种链式存储结构，链表属于线性表，采用链式存储结构，也是常用的动态存储方法。链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。 以“结点的序列”表示线性表称作线性链表（单链表） 单链表是链式存取的结构，为找第 i 个数据元素，必须先找到第 i-1 个数据元素。 因此，查找第 i 个数据元素的基本操作为：移动指针，比较 j 和 i 单链表 1、链接存储方法 链接方式存储的线性表简称为链表（Linked List）。 链表的具体存储表示为： ① 用一组任意的存储单元来存放线性表的结点（这组存储单元既可以是连续的，也可以是不连续的） ② 链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址（或位置）信息（称为指针（pointer）或链(link)） 注意： 链式存储是最常用的存储方式之一，它不仅可用来表示线性表，而且可用来表示各种非线性的数据结构。 2、链表的结点结构 ┌───┬───┐ │data │next │ └───┴───┘ data域--存放结点值的数据域 next域--存放结点的直接后继的地址（位置）的指针域（链域） 注意： ①链表通过每个结点的链域将线性表的n个结点按其逻辑顺序链接在一起的。 ②每个结点只有一个链域的链表称为单链表（Single Linked List）。 1.帐类表（KIND） 无索引 序号中文名称英文名称类型备注 1 帐类编号K_SERIAL byte 2 帐类名称K_NAME text*10 本表系统自动建立，共划分为15种帐类,不可增删 帐类编号帐类名称备注 0 上期结存进货，不参加进货统计 1 购入进货，购入时必需输入供货单位名称 2 自制进货 3 投资转入进货 4 盘盈进货 5 领料出库，领料必需输入领料部门名称 6 调拨出库 7 报损出库 8 盘亏出库 9 退库对低值易耗品，在用品退为在用库存 10 直接报废对于低值易耗品，在用品转报废 11 领用对于低值易耗品，在用库存转在用 12 调拨对于低值易耗品，在用库存减少 13 报废对于低值易耗品，在用库存报废 14 直进直出进出库，购入与领料对库存无影响 2.物品表（GOODS） 序号索引名称索引域唯一? 主索引? 1 G_CODING +G_CODING Y N 2 G_SERIAL +G_SERIAL Y Y 序号中文名称英文名称类型备注 1 物品内部编号G_SERIAL INT->long 系统内部唯一标识该物品 2 物品编号G_CODING TEXT * 10 用户使用此编号访问物品 &3 物品名称G_NAME TEXT*40 非空 &4 物品单位G_UNIT TEXT*8 非空 &5 物品规格G_STATE TEXT*20 6 物品类别G_CLASS INT 取自表CLASS 7 备注G_REMARKS MEMO 8 最小库存量G_MIN CURRENCY 为零，即无最小库存 9 最大库存量G_MAX CURRENCY 为零，即无最大库存 10 库存数量G_QUANT CURRENCY 控制出库数量 11 虚拟库存数量G_VQUANT CURRENCY 出库时用 12 库存金额G_AMOUNT CURRENCY 3.类别表（CLASS） 序号索引名称索引域唯一? 主索引? 1 C_CODING +C_CODING Y N 2 C_SERIAL +C_SERIAL Y Y 序号中文名称英文名称类型备注 1 类别内部序号C_SERIAL INT 系统内部唯一标识该物品 2 类别编号C_CODING TEXT *10 用户使用该编号访问类别信息 3 类别名称C_NAME TEXT*20 非空 4 出库类型C_KIND BYTE 1.移动平均 2..先进先出 3.后进先出 4.实际计价 *5.月末平均 5 备注C_REMARKS MEMO *6 底标志C_BOTTOM BOOLEAN *7 类别级别C_LEVEL BYTE 4.供货单位、使用部门(DEPART) 序号索引名称索引域唯一? 主索引? 1 D_CODING +D_CODING Y N 2 D_SERIAL +D_SERIAL Y Y 序号中文名称英文名称类型备注 1 内部序号D_SERIAL INT 系统内部唯一标识该部门 >0 供货单位 =0 库房 <0 使用部门 2 单位编号D_CODING TEXT*10 实验名称：实验一单链表的基本操作 实验目的 熟练掌握线性表两类存储结构的描述方法。 实验内容 从键盘读入若干个整数，建一个整数单链表，并完成下列操作： （1）打印该链表； （2）在链表中插入一个结点，结点的数据域从键盘读入，打印该链表； （3）在链表中删除一个结点，被删结点的位置从键盘读入，打印该链表； （4）在链表中做查找：从键盘读入要查找的整数，将该整数在链表中的位置打印出来，若要查找的整数不在链表中，返回一个信息。 算法设计分析 （一）数据结构的定义 单链表存储结构定义为： struct Node; typedef struct Node * pnode; struct Node { int info; pnode link; }; typedef struct Node * LinkList; （二）总体设计 程序由主函数、创建单链表函数、链表长度函数、链表打印函数、插入正整数函数、删除函数、查询函数组成。其功能描述如下： （1）主函数：调用各个函数以实现相应功能 int main(void) //主函数 { printf("单链表的基本操作实验：\n"); struct list *pnode; pnode = creat(); //创建 print(pnode); //输出 insert(pnode); //插入 print(pnode); //输出 _delete(pnode); //删除 print(pnode); //输出 _located(pnode); //查找 print(pnode); //输出 return 0 ; } （三）各函数的详细设计： Function1: struct list *creat()//创建链表； 第7章数据库设计 1．试述数据库设计过程。 答：这里只概要列出数据库设计过程的六个阶段：( l ）需求分析；( 2 ）概念结构设计；( 3 ）逻辑结构设计；( 4 ）数据库物理设计；( 5 ）数据库实施；( 6 ）数据库运行和维护。这是一个完整的实际数据库及其应用系统的设计过程。不仅包括设计数据库本身，还包括数据库的实施、运行和维护。设计一个完善的数据库应用系统往往是上述六个阶段的不断反复。 2 ．试述数据库设计过程各个阶段上的设计描述。 答：各阶段的设计要点如下：( l ）需求分析：准确了解与分析用户需求（包括数据与处理）。( 2 ）概念结构设计：通过对用户需求进行综合、归纳与抽象，形成一个独立于具体DBMS 的概念模型。( 3 ）逻辑结构设计：将概念结构转换为某个DBMS 所支持的数据模型，并对其进行优化。( 4 ）数据库物理设计：为逻辑数据模型选取一个最适合应用环境的物理结构（包括存储结构和存取方法）。( 5 ）数据库实施：设计人员运用DBMS 提供的数据语言、工具及宿主语言，根据逻辑设计和物理设计的结果建立数据库，编制与调试应用程序，组织数据入库，并进行试运行。( 6 ）数据库运行和维护：在数据库系统运行过程中对其进行评价、调整与修改。 3 ．试述数据库设计过程中结构设计部分形成的数据库模式。 答：数据库结构设计的不同阶段形成数据库的各级模式，即：( l ）在概念设计阶段形成独立于机器特点，独立于各个DBMS 产品的概念模式，在本篇中就是 E 一R 图；( 2 ）在逻辑设计阶段将 E 一R 图转换成具体的数据库产品支持的数据模型，如关系模型，形成数据库逻辑模式，然后在基本表的基础上再建立必要的视图( Vi 娜），形成数据的外模式；( 3 ）在物理设计阶段，根据DBMS 特点和处理的需要，进行物理存储安排，建立索引，形成数据库内模式。 4 ．试述数据库设计的特点。 答：数据库设计既是一项涉及多学科的综合性技术又是一项庞大的工程项目。其主要特点有：( l ）数据库建设是硬件、软件和干件（技术与管理的界面）的结合。( 2 ）从软件设计的技术角度看，数据库设计应该和应用系统设计相结合，也就是说，整个设计过程中要把结构（数据）设计和行为（处理）设计密切结合起来。 5 ．需求分析阶段的设计目标是什么？调查的内容是什么？ 答：需求分析阶段的设计目标是通过详细调查现实世界要处理的对象（组织、部门、企业等），充分了解原系统（手工系统或计算机系统）工作概况，明确用户的各种需求，然后在此基础上确定新系统的功能。调查的内容是“数据’夕和“处理”，即获得用户对数据库的如下要求：( l ）信息要求，指用户需要从数据库中获得信息的内容与性质，由信息要求可以导出数据要求，即在数据库中需要存储哪些数据；( 2 ）处理要求，指用户要完成什么处理功能，对处理的响应时间有什么要求，处理方式是批处理还是联机处理；( 3 ）安全性与完整性要求。 6 ．数据字典的内容和作用是什么？ 答：数据字典是系统中各类数据描述的集合。数据字典的内容通常包括：( l ）数据项；( 2 ）数据结构；( 3 ）数据流；( 4 ）数据存储；( 5 ）处理过程五个部分。其中数据项是数 #include if(!p||j>i-1) return; lnode *s=new lnode; s->data=e; s->next=p->next; p->next=s; }//插入 void deletelist(lnode *&head,int i,int &e){ lnode *p=head; int j=0; while(p->next&&j 单链表 1 题目编写一个程序，实现链表的各种基本运算，包括：链表操作：初始化链表、输出链表、输出链表长度和释放链表链表元素操作：插入元素、删除元素、输出元素（注意元素的位置） 2 目标熟悉单链表的定义及其基本操作的实现 3 设计思想 链表由多个结点通过next 指针连接成一个完整的数据结构，每个几点包括一个数据域和一个指向下一个结点的next 指针。通过对指针的改写与结点的增减，我们可以实现单链表的插入、删除、输入、输出、求长等操作。 4 算法描述 （1 ）初始化链表：输入元素个数n ，分配n 个结点空间，输入元素值，按元素顺序初始化next 指针，使之连接成串，尾指针赋值NULL 。 （2 ）输出链表：从表头开始沿next 指针遍历各结点，每次访问结点输出结点数据值，直至next 为空。 （3 ）输出链表长度：从表头开始沿next 指针遍历各结点，每次访问结点计数器加一，直至next 为空，返回计数器值。 （4 ）释放链表：沿next 指针从前向后依次释放结点，直至next 指空。 （5 ）插入元素：指针沿next 指向移动指定位，新分配一个空间并存入数据，其next 赋值为当前指针指向结点的next ，修改当前指针指向结点的next 指向新加结点。 （6 ）删除元素：指针沿next 指向移动指定位，修改待删结点的前一结点的next 指针指向待删结点的下一结点，保存数值，释放删除结点。 （7 ）输出元素：指针沿next 指向移动指定位，指针指向结点数据区，读出数值返回。 5 程序结构图 6源程序 #i nclude #i nclude 一、数据库结构设计步骤 二、需求分析 三、概念结构设计 四、逻辑结构设计 五、数据库物理设计 数据库结构设计 一、数据库结构设计步骤 一般可将数据库结构设计分为四个阶段，即需求分析、概念结构设计、逻辑结构设计和物理设计。 下面各节分别介绍各阶段设计内容和具体方法。 二、需求分析 需求分析的任务是具体了解应用环境，了解与分析用户对数据和数据处理的需求，对应用系统的性能的要求，提出新系统的目标，为第二阶段、第三阶段的设计奠定基础。一般需求分析的操作步骤如下所述。 1．了解组织、人员的构成 子系统的划分常常以现有组织系统为基础，再进行整合，而新系统首先必须达到的目的是尽可能地完成当前系统中有关信息方面的工作，在原有系统中，信息处理总是由具体人来实施的。我们要了解组织结构情况、相互之间信息沟通关系、数据（包括各种报告、报表、凭证、单据）往来联系情况。 具体弄清各个数据的名称，产生的时间与传递所需时间与周期，数据量的大小，所涉及（传送）的范围，使用数据的权限要求，数据处理过程中容易发生的问题及其影响，各个部门所希望获得的数据的情况等。 然后了解每个人对每一具体数据处理的过程，基本数据元素来源于哪些地方、获取的途径、处理的要求、数据的用途，进而弄清数据的构成、数据元素的类型、性质、算法、取值范围、相互关系。 在上述调查基础上，首先画出组织机构及工作职能图。我们以一个学校的基层单位——某大学一个系的管理为例来简要说明。 系的组织机构及工作职能如图7.1所示。 图7．1 系管理体系结构图 作为管理层经常需要的信息和工作有： ．查询老师个人基本情况及打印相应内容 ．查询与统计科研项目情况及相关报表 ．查询与统计论文著作情况及相关报表 ．上级部门及其他部门来文管理与查询（要求能全文检索） ．系部发文管理 ．任务下达、检查及管理 ．信件、通知的收发及管理 ．日程安排调度及管理 ．设备仪器计划及管理 ．设备入库与库存情况管理与查询 ．设备借还领用管理及相应报表 ．耗材计划与领发管理及相应统计报表 ．图书管理及借还情况查询 ．学生毕业设计文档管理 ．专业与班组编制与查询 ．教学文档管理及查询（安排与检查，包括课表、考试日程安排、监考安排等）．学生成绩管理与查询和统计 ．教师、学生、实验室课表管理及查询 ．学生基本情况管理与查询（包括社会活动、奖惩、家庭情况及学校校友管理） #include } LinkList InitList(void) { int i=1; char ch;//判断是否还输入 LinkList head=0,r,t;//r指向新创建的结点,t指向r的前一个结点 head=(struct nodes *)malloc(sizeof(struct nodes)); if(!head) { printf("存储空间分配失败\n"); return 0; } head->front=head; head->next=head; head->data='a'; t=r=head; while(1) { r=(struct nodes *)malloc(sizeof(struct nodes)); if(!r) { printf("存储空间分配失败\n"); return 0; } 数据库表结构设计参考． ）表名外部单位表（DeptOut 约束条件非空空数据类型（精度范围） /列名外部单位ID N 变长字符串(50) 主键 N 变长字符串类型 (50) N 单位名称(255) 变长字符串 (50) 单位简称变长字符变长字符(255)单位全交换类交换、市机、直送、邮变长字符(50)N (6)单位邮变长字符 变长字符(50))单位标英整排序(4) (50)交换变长字符变长字符(50)单位领 变长字符单位电(50) 变长字符所属城(50) 变长字符(255)单位地 备(255) 变长字符 补充说300条左右，一般不做修改。初始化记录该表记录数 表外部单位子表DeptOutSu 数据类型（精度范围列非约束条 变长字符(50)外部子单IDN 外ID变长字符(50)N单位名N变长字符(255) 变长字符单位编(50) 该表记录数一般很补充说 表内部单位表DeptI 数据类型（精度范围非列约束条IDN(50)变长字符主内部单类N变长字符(50) (255)变长字符N单位名 (50)变长字符单位简 变长字符单位全(255) 工作职 排序整(4) 单位领导(50) 变长字符串 (50) 单位电话（分机）变长字符串 (255) 变长字符串备注． 条以内），一般不做修改。维护一次后很少修改补充说明该表记录数较小（100 内部单位子表（DeptInSub）表名 约束条件数据类型（精度范围）空列名/非空 (50) N 变长字符串内部子单位ID 变长字符串(50) 父ID N 外键 (255) 单位名称 N 变长字符变长字符(50)单位编领导、部变长字符(50)单位类 Int 排序 该表记录数一般很补充说 省、直辖市表Provinc表 数据结构C语言版循环链表表示和实现.txt37真诚是美酒，年份越久越醇香浓烈；真诚是焰火，在高处绽放才愈显美丽；真诚是鲜花，送之于人，手有余香。/* 数据结构C语言版循环链表表示和实现 P35 编译环境：Dev-C++ 4.9.9.2 日期：2011年2月10日 */ #include 实验名称：链表 班级：学号___________姓名：报告日期： 一、实验目的及要求 1. 掌握单链表的存储结构形式及其描述。 2. 掌握单链表的建立、查找、插入和删除操作。 二、实验内容 1. 编写函数，实现随机产生或键盘输入一组元素，建立一个带头结点的单链表（无序）。 2. 编写函数，实现遍历单链表。 3. 编写函数，实现把单向链表中元素逆置（不允许申请新的结点空间）。 4. 编写函数，建立一个非递减有序单链表。 5. 编写函数，利用以上算法，建立两个非递减有序单链表，然后合并成一个非递减链表。 6. 编写函数，在非递减有序单链表中插入一个元素使链表仍然有序。 7. 编写函数，实现在非递减有序链表中删除值为x的结点。 8. 编写一个主函数，在主函数中设计一个简单的菜单，分别调试上述算法。 三、实验结果 四、实验总结： 这次实验使我在已经掌握单链表的存储结构，单链表的建立、查找、插入和删除操作的思想的基础上，可以对其利用C语言进行编程的实现，不仅对单链表的有关内容有了更深的理解，同时也对C语言编程的学习有了很大的进步。期间也遇到不少麻烦，；例如在编好程序后，编译运行时出现很多错误，但是在同学和网络的帮助下，将其成功解决。此外，需要注意的就是在用C语言进行编程时，一定要细心，注意基础知识的积累。同时算法思想也很重要。 源代码： #include typedef struct LNode { ElemType data; struct LNode *next; }LNode,*Linklist; void Createlist(Linklist &L) { Linklist p,s; ElemType x; L=(Linklist)malloc(sizeof(LNode)); L->next=NULL; p=L; scanf("%d",&x); while(x) { s=(Linklist)malloc(sizeof(LNode)); s->data=x; s->next=NULL; p->next=s; p=s; scanf("%d",&x);} } void printlist(Linklist &L) { Linklist p; p=L; while(p->next!=NULL){ p=p->next; printf("%d ",p->data);} printf("\n"); } void nizhi(Linklist &L) { Linklist p,s; p=L->next; L->next=NULL; while(p) { s=p; p=p->next; s->next=L->next; L->next=s;} } void charu(Linklist &L,ElemType x) 目录 1 选题背景 (1) 2 方案与论证 (2) 2.1 链表的概念和作用 (2) 2.3 算法的设计思想 (3) 2.4 相关图例 (4) 2.4.1 单链表的结点结构 (4) 2.4.2 算法流程图 (4) 3 实验结果 (5) 3.1 链表的建立 (5) 3.2 单链表的插入 (5) 3.3 单链表的输出 (6) 3.4 查找元素 (6) 3.5 单链表的删除 (7) 3.6 显示链表中的元素个数（计数） (8) 4 结果分析 (9) 4.1 单链表的结构 (9) 4.2 单链表的操作特点 (9) 4.2.1 顺链操作技术 (9) 4.2.2 指针保留技术 (9) 4.3 链表处理中的相关技术 (9) 5 设计体会及今后的改进意见 (10) 参考文献 (11) 附录代码： (12) 1 选题背景 陈火旺院士把计算机60多年的发展成就概括为五个“一”：开辟一个新时代----信息时代，形成一个新产业----信息产业，产生一个新科学----计算机科学与技术，开创一种新的科研方法----计算方法，开辟一种新文化----计算机文化，这一概括深刻影响了计算机对社会发展所产生的广泛而深远的影响。 数据结构和算法是计算机求解问题过程的两大基石。著名的计算机科学家P.Wegner指出，“在工业革命中其核心作用的是能量，而在计算机革命中其核心作用的是信息”。计算机科学就是“一种关于信息结构转换的科学”。信息结构（数据结构）是计算机科学研究的基本课题，数据结构又是算法研究的基础。 2 方案与论证 2.1 链表的概念和作用 链表是一种链式存储结构，链表属于线性表，采用链式存储结构，也是常用的动态存储方法。链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。 以“结点的序列”表示线性表称作线性链表（单链表） 单链表是链式存取的结构，为找第 i 个数据元素，必须先找到第 i-1 个数据元素。 因此，查找第 i 个数据元素的基本操作为：移动指针，比较 j 和 i 单链表 1、链接存储方法 链接方式存储的线性表简称为链表（Linked List）。 链表的具体存储表示为： ① 用一组任意的存储单元来存放线性表的结点（这组存储单元既可以是连续的，也可以是不连续的） ② 链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址（或位置）信息（称为指针（pointer）或链(link)） 注意： 链式存储是最常用的存储方式之一，它不仅可用来表示线性表，而且可用来表示各种非线性的数据结构。 2、链表的结点结构 ┌───┬───┐ │data │next │ └───┴───┘ data域--存放结点值的数据域 next域--存放结点的直接后继的地址（位置）的指针域（链域） 注意： ①链表通过每个结点的链域将线性表的n个结点按其逻辑顺序链接在一起的。 ②每个结点只有一个链域的链表称为单链表（Single Linked List）。数据库表结构设计参考
数据结构—链表应用能力测评
数据库设计各阶段
数据结构 单链表详解
数据库设计的基本步骤
数据结构课程设计单链表操作
数据结构课程设计单链表
进销存数据库表结构设计
数据结构(C语言)单链表的基本操作
数据库课后题答案 第7章 数据库设计
数据结构链表代码
数据结构与算法问题分析与源代码之单链表
数据库结构设计
数据结构双向链表实战应用(c语言源程序)
数据库表结构设计参考
数据结构C语言版 循环链表表示和实现
数据结构实验 链表
数据结构课程设计单链表
相关主题
文本预览