第一次上机实验链表

1、第一次上机实验一、 上机实验题目针对线性表、栈、队列，编程实现选择顺序和链式结构下数据结构建立、元素、删除等基本操作，并演示实际例子运行结果。二、相关技术或知识依靠链表实现对对象的处理，并通过对子函数的调用实现各子功能，例如在线性表中和删除元素，栈的出入栈操作和队列的进队出队操作。三、算法及数据结构设计设线性表采用带表头附加结点的单链表结构，编写线性表抽象数据类型各基本操作的实现函数。同时建立一个验证操作实现的主函数文件“链表.cpp”，编译并调试程序，直到正确运行。提示： 单向链表的结构定义如下：typedef struct Nodedata; /数据域struct Node * pNext

2、; /指针域NODE 为线性表设计基本操作：PNODE create_list(void);/创建链表/遍历链表/判断链表是否为空/求链表长度/*在 pHead 所指向链表void booltraverse_list(PNODE pHead); is_empty(PNODE pHead); length_list(PNODE); insert_list(PNODE pHead,void);的第个节点的前面一个新的结点，该节点的值是 val， 并且的值是从 1 开始*/bool delete_list(PNODE pHead,* pVal);/*删除链表第个节点，并将删除的结点的值存入 pVal

3、 所指向的变量中, 并且的值是从 1 开始*/void sort_list(PNODE);/对链表进行排序四、上机环境上机环境：VC 6.0五、源程序和运行结果源程序：# include # include # include typedef struct Node使用语言： C操作系统：win7 旗舰版data; /数据域struct Node * pNext; /指针域NODE, *PNODE;/函数PNODE create_list(void);/创建链表void traverse_list(PNODE pHead);/遍历链表bool is_empty(PNODE pHead);/判断

4、链表是否为空 length_list(PNODE);/求链表长度);/*在 pHead 所指向链表的第个节点的前面插void insert_list(PNODE pHead,入一个新的结点，该节点的值是 val， 并且的值是从1开始*/bool delete_list(PNODE pHead,* pVal);/*删除链表第个节点，并将删除,的结点的值存入 pVal 所指向的变量中,并且的值是从1开始*/void sort_list(PNODE);/对链表进行排序/*主界面*/_select()sn;prpr pr pr pr pr pr pr prf(=n);1.链2.数删输0.退表建数排数数

5、立n);据n);序n);据n);据n);f(f(f(f(f(f(据除出出n);f(=n);f(请选择0-5:n);for(;)scanf(%d,&sn); if (sn5)prf(nt 输入错误，重选0-5n); elsebreak;return sn;/*主函数*/ void main()PNODE pHead = NULL;val; j,k;while(1) switenu_select()case 1:pr pr prf(*n);链表的建立f(n);f(*n);pHead = create_list();break; case 2:prf(*n); prf(添加数据n);prf(请输入要

6、的位置：n); fflush(stdin);scanf(%d,&k); insert_list(pHead, k); traverse_list(pHead); break;case 3:prf(*n); prf(数 据 排 序n);prf(*n); sort_list(pHead);traverse_list(pHead); break;case 4:prf(*n); prf(删除数据n);prf(*n); prf(请输入要删除的位置：n);fflush(stdin); scanf(%d,&j);if ( delete_list(pHead, j ,&val) )prf(删除成功，您删除的元

7、素是: %dn, val);elseprf(删除失败!您删除的元素不存在!n);traverse_list(pHead);break;case 5:prf(*n); prf(输出所有数据n);prf(*n); traverse_list(pHead);break; case 0:prf(再见！n); getchar();return;/*建立链表*/ PNODE create_list(void)len;/用来存放有效节点的个数 i;val; /用来临时存放用户输入的结点的值 PNODE pHead = (PNODE)malloc(sizeof(NODE); if (NULL = pHead)

8、prf(分配失败, 程序终止!n); exit(-1);PNODE pTail = pHead; pTail-pNext = NULL;prf(请输入您需要生成的链表节点的个数: len = ); scanf(%d, &len);for (i=0; idata = val; pTail-pNext = pNew; pNew-pNext = NULL; pTail = pNew;return pHead;/*遍历链表*/ void traverse_list(PNODE pHead)PNODE p = pHead-pNext; while (NULL != p)prf(%d, p-data);

9、p = p-pNext;prf(n); return;bool is_empty(PNODE pHead)if (NULL = pHead-pNext) return true;elsereturn false;/*链表求长*/ length_list(PNODE pHead)PNODE p = pHead-pNext; len = 0;while (NULL != p)+len;p = p-pNext;return len;/*链表排序*/ void sort_list(PNODE pHead)i, j, t;len = length_list(pHead); PNODE p, q;for

10、(i=0,p=pHead-pNext; ipNext)for (j=i+1,q=p-pNext; jdata q-data)t = p-data;p-data = q-data;q-data = t;-pNext)return;/在 pHead 所指向链表的第个节点的前面一个新的结点，该节点的值是 val，并且的值是从1开始/*元素*/void insert_list(PNODE pHead,i = 0;PNODE p = pHead;while (NULL!=p & ipNext;+i;)if (i-1 | NULL=p)prf(错误n);/分配新的结点PNODE pNew = (PNODE

11、)malloc(sizeof(NODE); if (NULL = pNew)prf(动态分配内存失败!n); exit(-1);prf(请输入一个数据n); scanf(%d,&pNew-data) ;/将新的结点存入 p 节点的后面PNODE q = p-pNext; p-pNext = pNew; pNew-pNext = q;prf(成功n);/*元素删除*/bool delete_list(PNODE pHead,i = 0;PNODE p = pHead;,* pVal)while (NULL!=p-pNext & ipNext;+i;if (i-1 | NULL=p-pNext)r

12、eturn false;PNODE q = p-pNext;/q 指向待删除的结点*pVal = q-data;/删除 p 节点后面的结点p-pNext = p-pNext-pNext;/q 所指向的节点所占的内存free(q);q = NULL;return true;窗口运行结果为;=1.链 表 建 立2.数 据数删输0.退据除出出排数数序据据=请选择0-5:1*链表的建立*请输入您需要生成的链表节点的个数: len = 10请输入第1个节点的值:请输入第2个节点的值:请输入第3个节点的值:请输入第4个节点的值:请输入第5个节点的值:请输入第6个节点的值:请输入第7个节点的值:请输入第8个

13、节点的值:请输入第9个节点的值:1223432214543653414请输入第10个节点的值: 123=1.链2.数删输0.退表建数排数数立据序据据据除出出=请选择0-5:5*输出所有数据* 12 23 432 21 45 43 65 34 14 123=1.链2.数删输0.退表建数排数数立据序据据据除出出=请选择0-5:3*数 据 排 序* 12 14 21 23 34 43 45 65 123 432=1.链2.数删输0.退表建数排数数立据序据据据除出出=请选择0-5:4*删除数据*请输入要删除的位置：3删除成功，您删除的元素是: 2112 14 23 34 43 45 65 123 432=1.链2.数删输0.退表建数排数数立据序据据据除出出=请选择0-5:2*添加数据请输入要6的位置：请输入一个数据1234成功12 14 23 34 43 1234 45 65 123 432=1.链2.3.数表建数排立据序据删输0.退除 数 据出 数 据