单链表的实现和部分操作实验报告2（含完整代码） |
您所在的位置：网站首页 › jquery实验报告单 › 单链表的实现和部分操作实验报告2（含完整代码） |
单链表的实现和部分操作实验报告2（含完整代码）
|
仅供参考，记得看看自己班的课代表有没有发模板哦2333 实 验 报 告 课 程： 数据结构 班 级： 实验序号： 姓 名： 学 号: 实验日期： 题 目: 单链表基本操作的实现 一、实验目的和要求 ①熟悉C语言的上机环境，进一步掌握C语言的结构特点。 ②熟练掌握单链表的结构特点和基本操作。 ③学会使用单链表解决实际问题。 二、实验环境 Windows2000 ,VB 三、实验内容及实施 （1）实验内容： ①创建一个带头结点的单链表（头指针为head），且遍历此链表（输出链表中各结点值） 定义一个函数 CreateList (LinkList &L, int n) 和 输出函数 print(LinkList &L) ②查找单链表中的第i个结点，并输出结点元素的值 定义一个函数 GetElem(LinkList L, int i, ElemType &target) ③在单链表中的第i个结点前插入一个结点值为e的正整数(从外部输入) 定义一个函数 ListInsert(LinkList &L, int i, ElemType e) ④删除单链表中的第j个结点 定义一个函数 ListDelete(LinkList &L, int j) ⑤将单链表中的各结点就地逆序（不允许另建一个链表） 定义一个函ListReverse(LinkList &L) （2）源程序 #include #include #include #include #define MAXSIZE 100 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 #define LIST_INIT_SIZE 5 #define LISTINCREMENT 1 using namespace std; typedef int Status; typedef int ElemType; //表内元素类型为 int, 可更改 typedef struct LNode { ElemType Data; struct LNode *next; }LNode, *LinkList; int n, i, j; //全局变量 ElemType e; Status InitList (LinkList &L) { L = new LNode; L -> next = NULL; return OK; } void print(LinkList &L) //遍历此链表（输出链表中各结点的值） { printf("The new linear table is as follow:\n"); LinkList p = L; while(p -> next) { p = p -> next; cout Data > n; printf("Please enter the elements:\n"); L = new LNode; L -> next = NULL; LinkList r = L; for(int i = 0; i < n; ++i) { LinkList p = new LNode; cin >> p -> Data; r -> next = p; r = p; } r -> next = NULL; print(L); } Status GetElem(LinkList L, int i, ElemType &target) //查找单链表中的第i个结点，并输出结点元素的值， 用一个 target 是可以把这个值取出来，也许还有其他用处 { printf("Please enter the position to find:\n"); cin >> i; LinkList p = L -> next; int j = 1; while(p && j < i) { p = p -> next; ++j; } if(!p || j > i) return ERROR; target = p -> Data; cout i >> e; while(p && j < i-1) { p = p -> next; ++j; } if(!p || j > i-1) return ERROR; LinkList q = new LNode; q -> Data = e; q -> next = p -> next; p -> next = q; print(L); return OK; } Status ListDelete(LinkList &L, int j) //删除单链表中的第j个结点 { printf("Enter the position of the element to delete:\n"); cin >> j; LinkList p = L; int i = 0; while((p -> next) && (i < j-1)) //删除第个 j 结点， 让指向第 j-1 个结点， 方便删掉其下一个即第 j 个结点 { p = p -> next; ++i; } if(!(p -> next) || (i > j-1)) return ERROR; LinkList q = p -> next; p -> next = q -> next; delete q; print(L); return OK; } Status ListReverse(LinkList &L) //将单链表中的各结点就地逆序（不允许另建一个链表） { LinkList p = L -> next; //一直用指针 p 指向最初的首元结点，逆序后成为尾结点 if(p) { LinkList q = p -> next; //指向 p 的下一结点 if(q) while(q) { p -> next = q -> next; //连上 q 的下一结点，把 q 取出来 q -> next = L -> next; //把 q 插到头结点之后 L -> next = q; q = p -> next; //指向 p 的下一结点 } } print(L); return OK; } int main() { int num; ElemType target; LinkList head; printf("What do you want to do?\n"); printf("0.退出程序\n"); printf("1.创建一个带头结点的单链表（头指针为head），且遍历此链表（输出链表中各结点的值）\n"); printf("2.查找单链表中的第i个结点，并输出结点元素的值\n"); printf("3.在单链表中的第i个结点前插入一个结点值为e的正整数(从外部输入)\n"); printf("4.删除单链表中的第j个结点\n"); printf("5.将单链表中的各结点就地逆序（不允许另建一个链表）\n"); printf("Please enter the serial number of the operation you want to perform:\n"); while(cin >> num) { switch(num) { case 0: exit(0); case 1: InitList(head); CreateList(head, n); break; case 2: GetElem(head, i, target); break; case 3: ListInsert(head, i, e); break; case 4: ListDelete(head, j); break; case 5: ListReverse(head); break; default: printf("The serial number is illegal.Please enter again:\n"); } printf("\nPlease enter the serial number of the operation you want to perform:\n"); } return 0; }（3）实验结果 
四、实验感想 通过这次实验，同时对比顺序表的学习，我初步掌握了单链表的结构特点和基本操作，巩固了C语言相关的程序设计方法与技术，并且意识到，熟练掌握课本知识是实验的基础，不把课本上的相关知识学深学透， 实验便无从着手， 另外，在做实验的过程锻炼思考问题并动手解决的能力很重要。 PS：在这里面，就地逆序应该算一个小小的重头戏（滑稽） 这个实验里是定住首元结点，每次都把连在首元结点后的结点摘下来插到头指针之后 画图是这样的， 借用老师课件 另一种方法是 用三个指针， 让后一个的 next 指针指向前面，因为从尾部往前指较难实现，所以这里从 head 指针的后面，通过三个指针慢慢向尾部推进， 实现所有 next 指针反向 班里大佬的代码和配图 void reverse(Plist list)//逆置 { Plist pre, cur, rear; pre = list; if (pre->next == NULL) { printf("该链表只有一个元素，无需置换"); exit(0); } pre = list->next; cur = pre->next; pre->next = NULL; while(cur) { rear = cur->next;//防止cur最后为空时rear找不到cur所指的next cur->next = pre; pre = cur; cur = rear; } list->next = pre; printf("逆置完成\n");
刚开始接触上手都难，如果程序一直运行不出来，注意创建链表那块儿， 再好好跟课本上的标准代码比对， 康康你有没有这样 如果还有一丝丝疑惑 ，接着向下看（打出来的字绝对不能白费） head 申请了空间， 是一个结点， 而 head->next 未赋值， 所以指向是随机的（这很危险），我们让 head->next = p 的前提是 p 是一个结点， 是已经通过 malloc 或 new 申请了空间的结点，让上一个结点的 next 指针指向下一个结点， 这样就把两个结点串了起来 而在head->next 未赋值的情况下，p＝head-＞next 是没有任何意义的 我那个程序创建的过程是下面这个丑图，r -> next = p 的过程就是横着的那个箭头，意会一下？ 
解释一下就是： 在单链表尾部连上一个结点之后，让 r 指向链表的尾部， 申请新结点 p，输入数据值，通过 r -> next = p 把 p 连在 r 的后面，即把 p 接在链表尾部， 然后让 r 再次指向链表尾部(即 r = p )，如此这般，重复操作 这就是尾插创建单链表 如有不对，敬请指正呀 配图同时 get 到新技能 图片链接里面加上宽度百分比 |
也许还可以两端结点交换位置，直到中部（感觉没毛病，不过老师说这样不对）
等号是从右向左赋值的 我们并不想 让 p 指向 head -> next （此时 head -> next 是未定的啊喂 ）， 而是想让p 连在 head 后面， 就是让 head -> next = p 啊【本文地址】
今日新闻 |
推荐新闻 |