实验一 顺序表与链表
一、实验目的
1、掌握线性表中元素的前驱、后续的概念。
2、掌握顺序表与链表的建立、插入元素、删除表中某元素的算法。
3、对线性表相应算法的时间复杂度进行分析。
4、理解顺序表、链表数据结构的特点（优缺点）。
二、实验预习
说明以下概念
1、线性表：由n(n≥0)个数据特性相同的元素构成的有限序列
2、顺序表：用一组地址连续的存储单元依次存储线性表的数据元素、这种表示也称作线性表的顺序存储结构或顺序映像。通常，称这种存储结构的线性表为顺序表( Sequential List)。
3、链表：链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域
三、实验内容和要求
1、阅读下面程序，在横线处填写函数的基本功能。并运行程序，写出结果。
#include
#include
#define ERROR 0
#define OK 1
#define INIT_SIZE 5
#define INCREM 5
typedef int ElemType;
typedef struct Sqlist{
ElemType *slist;
int length;
int listsize;
}Sqlist;
int InitList_sq(Sqlist *L);
int CreateList_sq(Sqlist *L,int n);
int ListInsert_sq(Sqlist *L,int i,ElemType e);
int PrintList_sq(Sqlist *L);
int ListDelete_sq(Sqlist *L,int i);
int ListLocate(Sqlist *L,ElemType e);
int InitList_sq(Sqlist *L){
L->slist=(ElemType*)malloc(INIT_SIZE*sizeof(ElemType));
if(!L->slist) return ERROR;
L->length=0;
L->listsize=INIT_SIZE;
return OK;
}
int CreateList_sq(Sqlist *L,int n){
ElemType e;
int i;
for(i=0;i printf("input data %d",i+1); scanf("%d",&e); if(!ListInsert_sq(L,i+1,e)) return ERROR; } return OK; } int PrintList_sq(Sqlist *L){ int i; for(i=1;i<=L->length;i++) printf("%5d",L->slist[i-1]); return OK; } int ListInsert_sq(Sqlist *L,int i,ElemType e){ int k; if(i<1||i>L->length+1) return ERROR; if(L->length>=L->listsize){ L->slist=(ElemType*)realloc(L->slist, (INIT_SIZE+INCREM)*sizeof(ElemType)); if(!L->slist) return ERROR; L->listsize+=INCREM; } for(k=L->length-1;k>=i-1;k--){ L->slist[k+1]= L->slist[k]; } L->slist[i-1]=e; L->length++; return OK; } int ListDelete_sq(Sqlist *L,int i){ } int ListLocate(Sqlist *L,ElemType e){ } int main(void){ Sqlist sl; int n,m,k; printf("please input n:"); scanf("%d",&n); if(n>0){ printf("n1-Create Sqlist:n"); InitList_sq(&sl); CreateList_sq(&sl,n); printf("n2-Print Sqlist:n"); PrintList_sq(&sl); printf("nplease input insert location and data:(location,data)n"); scanf("%d,%d",&m,&k); ListInsert_sq(&sl,m,k); printf("n3-Print Sqlist:n"); PrintList_sq(&sl); printf("n"); } else printf("ERROR"); return 0; } please input n:5 1-Create Sqlist: input data 14 input data 26 input data 311 input data 44 input data 57 2-Print Sqlist: 4 6 11 4 7 please input insert location and data:(location,data) 2,45 3-Print Sqlist: 4 45 6 11 4 7 Press any key to continue 首先应该选择顺序表的动态存储方式进行顺序表结构的定义，然后在程序的开头进 行顺序表各种操作函数的声明以及预定义命令，接着编写各种操作函数的函数体，而在 主函数中要首先调用InitList_sq(&sl)函数初始化，然后调用InitList_sq()创建顺序 表，调用PrintList_sq()函数输出该顺序表中元素的值；然后调用ListInsert_sq() 函数，进行插入操作，并输出插入新元素后的状态。 删除算法代码： int ListDelete_sq(Sqlist *L,int i){ if (L->length==0) return 0; if(i<1||i>L->length) return 0; for(int j=i;j L->slist[j-1]=L->slist[j]; L->length--; return 1; } 运行结果 3-Print Sqlist: 4 45 6 11 4 7 please input delete location: 3 Delete date is:6 4-Print Sqlist: 4 45 11 4 7 查找算法代码： int ListLocate(Sqlist *L,ElemType e){ for(int i=1; i<=L->length;i++) {if(L->slist[i-1]==e) return i; return 0; }} 4-Print Sqlist: 4 45 11 4 7 please input date date 7 Search date is No5 3、阅读下面程序，在横线处填写函数的基本功能。并运行程序，写出结果。 #include #include #define ERROR 0 #define OK 1 typedef int ElemType; typedef struct LNode{ ElemType data; struct LNode *next; }LNode,*linkList; linkList CreateList(int n); void PrintList(linkList L); int GetElem(linkList L,int i,ElemType *e); linkList CreateList(int n){ LNode *p,*q,*head; int i; head=(linkList)malloc(sizeof(LNode)); head->next=NULL; p=head; for(i=0;i q=(linkList)malloc(sizeof(LNode)); printf("input data %i:",i+1); scanf("%d",&q->data); q->next=NULL; p->next=q; p=q; } return head; } void PrintList(linkList L){ LNode *p; p=L->next; while(p!=NULL){ printf("%5d",p->data); p=p->next; } } int GetElem(linkList L,int i,ElemType *e){ LNode *p;int j=1; p=L->next; while(p&&j p=p->next;j++; } if(!p||j>i) return ERROR; *e=p->data; return OK; } int main(void){ int n,i;ElemType e; linkList L=NULL; printf("please input n:"); scanf("%d",&n); if(n>0){ printf("n1-Create linkList:n"); L=CreateList(n); printf("n2-Print linkList:n"); PrintList(L); printf("n3-GetElem from linkList:n"); printf("input i="); scanf("%d",&i); if(GetElem(L,i,&e)) printf("No%i is %d",i,e); else printf("not exists"); }else printf("ERROR"); return 0; } please input n:5 1-Create Sqlist: input data 1:12 input data 2:8 input data 3:23 input data 4:9 input data 5:31 2-Print Sqlist: 12 8 23 9 31 3-GetElem from linklist: Input i=5 No5 is 31 Press any key to continue 4、为第3题补充插入功能函数和删除功能函数。并在主函数中补充代码验证算法的正确性。 插入算法代码： int InsertList(linkList &L,int i,ElemType e){ int j=0; LNode *p,*q; p=L->next; while(p&&j p=p->next;j++;} if(p==null||j>i-1) printf(“n i Error!”); else { q=(LNode *)malloc(sizeof(LNode)); q->data=e; q->next=p->next; p->next=q; } return OK; } 2-Print Sqlist: 12 8 23 9 31 3-GetElem from linklist: Input i=5 No5 is 31 4-Insert from linklist: Input i=2 Input e=16 12 16 8 23 9 31 删除算法代码： int DeleteList(linkList &L,ElemType e) { LNode *p,*q; p=L->next; while(p&&p->data!=e) {q=p;p=p->next;} if(!(p->next)||(j>i-1)) printf(“n i Error!”); else { q->next=p->next; delete q; return OK; } 4-Insert from linklist: Input i=2 Input e=16 12 16 8 23 9 31 5-Delete from linklist: Input e=23 12 16 8 9 31 Press any key to continue2、为第1题补充删除和查找功能函数，并在主函数中补充代码验证算法的正确性。
当在主函数里面调用删除功能函数并传参数进去时，程序将自动跳到函数体里面，
利用所传参数一步步执行，在该函数里面，当把顺序表和序号i传值进去时，程序可以先判断所传值是否满足条件，若满足，则开始从顺序表第一个元素开始依次遍历，直到
找到第i个位置的元素，并将其删除，后面的元素依次前移，填补。而表的长度则减一，
删除成功。若不满足，则返回0，表示删除失败。
当在主函数里面调用查找功能函数并传参数进去时，程序将自动跳到函数体里面，
利用所传参数一步步执行，在该函数里面，当把顺序表和要查找的值e传值进去时，程
序开始从顺序表第一个元素开始依次遍历，直到找到值为e的元素，并返回其位置序号，
查找成功。若遍历了顺序表所有元素依然没有符合条件的e的值，则返回0，表示查找
失败。
首先应该进行单链表结构的定义，然后在程序的开头进行顺序表各种操作函数的声
明以及预定义命令，接着编写各种操作函数的函数体，而在主函数中要首先调用
linkList CreateList(int n)创建带头结点的单链表，输入结点数，然后依次输入各个
结点的值。接着调用打印单链表功能函数输出单链表中的值。再调用查找功能函数，输
入查找元素的位置，输出对应元素的值。然后调用插入功能函数，输入要插入的位置和
元素，打印输出插入后的新链表。同理调用删除功能函数，输入要删除的元素值，最后
打印输出删除后的单链表。
在主函数里面调用查找功能函数并传参数进去时，程序将自动跳到函数体里面，
利用所传参数一步步执行，在该函数里面，当把单链表，要插入的位置序号和元素内容
传值进去时，程序开始从单链表第一个元素开始依次遍历，直到找到插入位置的前一个
节点，用指针p指向它。然后创建一个以e为值的新节点指针q，修改节点*q的next
域指向节点*p的下一个节点，再将节点*p的next域修改为指向新节点*s。返回ok，
表示插入成功。最后打印输出插入后的新链表。
当在主函数里面调用删除功能函数并传参数进去时，程序将自动跳到函数体里面，
利用所传参数一步步执行，在该函数里面，当把单链表，要删除的元素内容传值进去时，
开始从单链表第一个元素开始依次找，直到找到删除位置的前一个节点，用指针
p指向它。指针q指向要删除的节点。然后修改指针p的下一个为指向待删除节点*q
的后继节点。返回ok表示删除成功。最后打印输出删除后的新链表。
