数据结构验证作业概要.doc

《数据结构》实验报告一 一、上机实验的问题和要求： 单链表的查找、插入与删除。设计算法，实现线性结构上的单链表的产生以及元素的查找、插入与删除。具体实现要求： 从键盘输入20个整数，产生不带表头的单链表，并输入结点值。 从键盘输入1个整数，在单链表中查找该结点的位置。若找到，则显示“找到了”；否则，则显示“找不到”。 从键盘输入2个整数，一个表示欲插入的位置i，另一个表示欲插入的数值x，将x插入在对应位置上，输出单链表所有结点值，观察输出结果。 从键盘输入1个整数，表示欲删除结点的位置，输出单链表所有结点值，观察输出结果。 将单链表中值重复的结点删除，使所得的结果表中个结点值均不相同，输出单链表所有结点值，观察输出结果。 删除其中所有数据值为偶数的结点，输出单链表所有结点值，观察输出结果。 把单链表变成带表头结点的循环链表，输出循环单链表所有结点值，观察输出结果。 （★）将单链表分解成两个单链表A和B，使A链表中含有原链表中序号为奇数的元素，而B链表中含有原链表中序号为偶数的元素，且保持原来的相对顺序，分别输出单链表A和单链表B的所有结点值，观察输出结果。 二、程序设计的基本思想，原理和算法描述： 1、基本操作函数 link * get(link *l, int i)； //创建链表 link * ins (link *l, int a,int i) //在链表内插入值 link * find(link *l, int a)； //在链表内查找值 link * del(link *l, int i); //在链表内删除值 link * delrepeat( link *l); //在链表内删除重复值 link * deleven(link *l); //删除链表内偶数值 link * rotate(link *l); //形成循环链表 void divide(link *l); //分解成两个链表 coutendl; 2、基本操作 cout请选择您要的操作：; cout 1、插入; cout 2、查找; cout 3、删除; cout 4、删除重复结点; cout 5、删除偶数结点; cout 6、构建循环链表; cout 7、分解为两个链表; cout 0、退出; 三、源程序及注释： #include iostream using namespace std; typedef struct node { int data; struct node *next; }link; void print1(link *l); link * get(link *l, int i) { link *p; int j=0; p=l; while((ji) (p-next!=NULL)) { p=p-next;j++; } if(j==i) return p; else return NULL; } link * ins (link *l, int a,int i) { link *p,*s; p=get(l,i-1); if(p==NULL) cout输入有误endl; else { s=(link *)malloc(sizeof(link)); s-data=a; s-next=p-next; p-next=s; } return l; } link * find(link *l, int a) { link *p; int i=0; int j=0; p=l; while(p!=NULL) { i++; if(p-data!=a) p=p-next; else { cout您查找的数据在第i-1个位置.endl; j=1; p=p-next; } } if(j!=1) cout您查找的数据不在线性表中.endl; return l; } link * del(link *l, int i) { link *p,*s; p=get(l,i-1); if(p==NULL) cout输入有误endl; else { s=p-next; p-next=s-next; free(s); } return l; } link * delrepeat( link *l) // 删除相同元素并释放内存 { link *s, *r, *t; if ( l- next == NULL ) return l;