软基上机报告-链表(拓展题).doc

1、 程序流程说明2、 1）创建一个单链表，其数据元素为整数，从键盘输入，输入0结束（注意0不放到链表内）；3、 2）从键盘任意输入一个整数，在单链表中查询该数，如果单链表中已经存在这个数，就调用删除函数，删除该元素所在结点，并将单链表在删除前后的数据元素依次输出到屏幕上；4、 如果单链表中不存在这个数，就调用插入函数，将这个数插入到单链表尾，并将单链表在插入前后的数据元素依次输出到屏幕上。 5、 3）教材第一章习题第9题（用链表实现）ex2_3扩展题6、 1）删除单链表中全部的负数7、 2）创建一个双向链表，按照冒泡排序的思路对这个双向链表进行排序，打印排序结果。注意，本算法在交换元素时是将链点整个交换而不是将链点中的元素值交换。8、 9、10、11、2_21）创建一个单链表，其数据元素为整数，从键盘输入，输入0结束（注意0不放到链表内）；（if x！=0，scanf） 2）从键盘任意输入一个整数，在单链表中查询该数，如果单链表中已经存在这个数，就调用删除函数，删除该元素所在结点，并将单链表在删除前后的数据元素依次输出到屏幕上；（search 返回重复的位置，然后删除（同实验一） 如果单链表中不存在这个数，就调用插入函数，将这个数插入到单链表尾，并将单链表在插入前后的数据元素依次输出到屏幕上。（同实验一，直接加在链表末尾）3）判断插入元素与表内元素的大小，如temp-dataxlink-data，则插入temp后2_31）删除单链表中全部的负数（逐个判断是不是负数，并且返回负数所在位置，删除过春哥同实验一）2）创建一个双向链表，按照冒泡排序的思路对这个双向链表进行排序，打印排序结果。注意，本算法在交换元素时是将链点整个交换而不是将链点中的元素值交换。（从一开始逐个比较，将比第一位大的与第一位交换位置，一直比较到最后一位然后开始对于第二位重复比较）二、程序代码2_2#include#include#includetypedef struct Nodeint data;struct Node *link;node;typedef struct Listnode *head;node *tail;int length;list;void creat_list(list *table)int x,i;node *temp;table-head=NULL;table-tail=NULL;table-length=0; x=1;scanf(%d,&x);for(i=0;x!=0;i+)fflush(stdin);printf(n);temp=(node*)malloc(sizeof(node);temp-data=x;temp-link=NULL;temp-link=table-head;table-head=temp;table-length+;scanf(%d,&x);node * create_node(int new_node)node * temp;temp = (node*)malloc(sizeof(node);temp-data = new_node;temp-link = NULL;return temp;void get(list *table,int n)int i,loc=table-length+1;node *temp;node *newnode;temp=table-head;table-length+;newnode=create_node(n);for(i=2;ilink;newnode-link = temp-link; temp-link = newnode;void show_list(list *table)int x,i;node *temp;printf(链表为：n);temp=table-head;for(i=1;i length;i+)x=temp-data;printf(%d ,x);temp=temp-link;void delete_node(list *table,int n)int i;node *temp,*t;temp=table-head;if(n=1)temp=temp-link;table-head=temp;if(n2&nlength)temp=table-head;for(i=2;ilink;t=temp-link;temp-link=t-link; if(n=table-length)for(i=2;ilink; temp-link=NULL;if(n=2)temp=table-head;t=temp-link;temp-link=t-link;table-length-;void search(list *table,int x,int a2)int i=0,j=0;node *temp;temp=table-head;for(i=1;ilength;i+)if(x=temp-data)a1=i;j+;temp=temp-link;if(j=0)a0=0;a1=0;elsea0=1;void main()list table;int m,a2;creat_list(&table);show_list(&table);printf(n输入一个整数n);scanf(%d,&m);search(&table,m,a);if(a0=1)delete_node(&table,a1);show_list(&table);elseget(&table,m);show_list(&table);2_2(3)#include#include#includetypedef struct Nodeint data;struct Node *link;node;typedef struct Listnode *head;node *tail;int length;list;void creat_list(list *table)int x,i;node *temp;table-head=NULL;table-tail=NULL;table-length=0; x=1;scanf(%d,&x);for(i=0;x!=0;i+)fflush(stdin);printf(n);temp=(node*)malloc(sizeof(node);temp-data=x;temp-link=NULL;temp-link=table-head;table-head=temp;table-length+;scanf(%d,&x);node * create_node(int new_node)node * temp;temp = (node*)malloc(sizeof(node);temp-data = new_node;temp-link = NULL;return temp;void get(list *table,int n)int i,m=0;node *temp;node *newnode;temp=table-head;table-length+;newnode=create_node(n);if(ndata)newnode-link=temp;temp=newnode;elsefor(i=1;m=0;i+)if(ilength&temp-datan&nlink-data)newnode-link = temp-link; temp-link = newnode;m=1;else if(i=table-length)temp-link=newnode;newnode-link=NULL;m=1;temp=temp-link;table-length+;void show_list(list *table)int x,i;node *temp;printf(链表为：n);temp=table-head;for(i=1;i length;i+)x=temp-data;printf(%d ,x);temp=temp-link;void main()list table;int m,a2;creat_list(&table);show_list(&table);printf(n输入一个整数n);scanf(%d,&m);get(&table,m);show_list(&table);2_3(1)#include#include#includetypedef struct Nodeint data;struct Node *link;node;typedef struct Listnode *head;node *tail;int length;list;void creat_list(list *table)int x,i;node *temp;table-head=NULL;table-tail=NULL;table-length=0; x=1;scanf(%d,&x);for(i=0;x!=0;i+)fflush(stdin);printf(n);temp=(node*)malloc(sizeof(node);temp-data=x;temp-link=NULL;temp-link=table-head;table-head=temp;table-length+;scanf(%d,&x);node * create_node(int new_node)node * temp;temp = (node*)malloc(sizeof(node);temp-data = new_node;temp-link = NULL;return temp;void get(list *table,int n)int i,loc=table-length+1;node *temp;node *newnode;temp=table-head;table-length+;newnode=create_node(n);for(i=2;ilink;newnode-link = temp-link; temp-link = newnode;void show_list(list *table)int x,i;node *temp;printf(n链表为：n);temp=table-head;for(i=1;i length;i+)x=temp-data;printf(%d ,x);temp=temp-link;void delete_node(list *table,int n)int i;node *temp,*t;temp=table-head;if(n=1)temp=temp-link;table-head=temp;if(n2&nlength)temp=table-head;for(i=2;ilink;t=temp-link;temp-link=t-link; if(n=table-length)for(i=2;ilink; temp-link=NULL;if(n=2)temp=table-head;t=temp-link;temp-link=t-link;table-length-;void search(list *table,int a2)int i=0,j=0;node *temp;temp=table-head;for(i=1;ilength;i+)if(temp-datalink;if(j=0)a0=0;a1=0;elsea0=1;void paixu(list *table)int i,j,m,u;node *temp,*t,*p;for(i=1;ilength;i+)temp=table-head;for(u=1;ulink;t=temp;for(j=i;jlength;j+)temp=t;for(m=i;mlink;if(t-datadata)p=temp-link;temp-link=t-link;t-link=p;void main()list table;int m,a2;creat_list(&table);show_list(&table);search(&table,a);for(m=1;a0=1;m+)search(&table,a);if(a0=1)delete_node(&table,a1);show_list(&table);2_3（2）#include#include#includetypedef struct Nodeint data;struct Node *link,*last;node;typedef struct Listnode *head;node *tail;int length;list;void creat_list(list *table)int x,i;node *temp,*t,*p;table-head=NULL;table-tail=NULL;table-length=0; x=1;scanf(%d,&x);for(i=0;x!=0;i+)fflush(stdin);printf(n);temp=(node*)malloc(sizeof(node);temp-data=x;temp-link=NULL;temp-link=table-head;table-head=temp;table-length+;scanf(%d,&x);t=(node*)malloc(sizeof(node);t=table-head;t-last=NULL;for(i=2;ilength;i+)p=t;t=t-link;t-last=p;void show_list(list *table)int x,i;node *temp;printf(链表为：n);temp=table-head;for(i=1;i length;i+)x=temp-data;printf(%d ,x);temp=temp-link;void paixu(list *table)int i,j,m;node *temp,*t,*p,*q;temp=table-head;t=temp;for(i=2;ilength;i+)t=t-link;if(t-datatemp-data)p=t-link;t-link=temp-link;temp-link=p;t-last-link=temp;table-head=t;t-last=NULL;temp-last=t-last;p=t;t=temp;temp=t;/*/temp=table-head;for(i=2;ilength;i+)temp=temp-link;t=temp;for(j=i+1;jlength;j+)t=t-link;if(t-datatemp-data)p=t-link;t-link=temp-link;temp-link=p;t-last-link=temp;temp-last-link=t;p=t-last;t-last=temp-last;temp-last=p;p=t;t=temp;temp=t; void main()list table;creat_list(&table);show_list(&table); paixu(&