1、数据结构实验一 线性表基本操作实验一 线性表基本操作 一、实验目的掌握线性表的顺序表和链表的基本操作：建立、插入、删除、查找、合并、打印等运算。二、实验要求包含有头文件和main函数；1.格式正确，语句采用缩进格式； 2.设计子函数实现题目要求的功能；3.编译、连接通过，熟练使用命令键；4.运行结果正确，输入输出有提示，格式美观。三、实验设备、材料和工具1.奔腾2计算机或以上机型2.turboc2,win-tc四、实验内容和步骤实验内容：1.分析程序。2.用头插入法建立带头结点的单链表3.用尾插入法建立带头结点的单链表4.单链表就地逆置5.约瑟夫问题步骤：1.确定数据的结构；2.利用main函
2、数调用各子函数；3.调试、分析运行结果。五、实验报告要求1.根据实验内容初步设计好程序，并从理论上排除错误；2.针对程序的健壮性准备好测试数据；3.结果分析中如实填写运行后的结果，记录调试过程中产生的重要问题和解决方法。六、根据实验过程填写下面内容基础部分1请认真阅读理解，上机运行并分析结果。#include seqlist.h#include main( ) SeqList a; int i, m, x; printf(请输入顺序表元素，从小到大排列，元素为整型量，用空格分开，-99为结束标志 ：n); a.last = 0; i = 0; scanf(%d,&i); while (i !=
3、 -99) a.elema.last = i; a.last+; scanf(%d,&i); a.last-;scanf(%d,&x);for (i = 0; i = 0) & ( x = i + 1; m-) a.elemm + 1 = a.elemm; a.elemi + 1 = x; a.last+; for (i = 0; i = a.last; i+) printf(%4d,a.elemi); printf(n);结果：以上程序的功能是什么？功能是在顺序表中顺序插入一个数。（已修改无法插入于第一个数之前的错误）2下面的程序实现用头插法建立带头结点的单链表，请补充完整程序。#inclu
4、de #include #define ElemType char#define LEN sizeof(struct Node)typedef struct Node /*结点类型定义*/ ElemType data; struct Node * next;Node, *LinkList; /* LinkList为结构指针类型*/void CreateFromHead(LinkList L) int c; Node* pnew; printf(请输入char类型数据，（以*结束）); while(1) pnew=(Node*)malloc(LEN); scanf(%c,&pnew-data);
5、 if(pnew-data=*) break; pnew-next=L-next; L-next=pnew; pnew-next=NULL; return L;void main() LinkList l; Node *p; printf(用头插法建立单链表,请输入链表数据,以*结束!n); l=(LinkList)malloc(sizeof(Node); l-next=NULL; CreateFromHead(l); p = l-next; while(p!=NULL) printf(%cn,p-data); p=p-next; 思考：建立循环单链表修改头插法建表算法的那些语句可以完成？思考
6、结果： pnew-next=NULL;修改这句就可以了。改成pnew-next=L;3下面的程序实现用尾插法建立带头结点的单链表，请补充完整程序。#include #include #define ElemType char#define LEN sizeof(struct Node)typedef struct Node ElemType data; struct Node * next;Node, *LinkList; void init_linklist(LinkList *l);void CreateFromTail(LinkList L);void init_linklist(Lin
7、kList *l)/*对单链表进行初始化*/ *l=(LinkList)malloc(LEN); (*l)-next=NULL;void CreateFromTail(LinkList L) Node* pnew,*ptail; ptail=L; printf(请输入char类型数据，（以*结束）); pnew=(Node*)malloc(LEN); scanf(%c,&pnew-data); for(;pnew-data!=*;) ptail-next=pnew; ptail=pnew; pnew=(Node*)malloc(LEN); scanf(%c,&pnew-data); ptail
8、-next=NULL; return L; void main() LinkList l; Node *p; init_linklist(&l); printf(用尾插法建立单链表,请输入链表数据,以*结束!n); CreateFromTail(l); p = l-next; while(p!=NULL) printf(%cn,p-data); p=p-next; 思考：建立循环单链表修改尾插法建表算法的那些语句可以完成？思考结果： ptail-next=NULL;ptail-next不赋值NULL，改赋值为头节点地址提高部分4.已知一个带头结点的单链表L，设计算法实现：以表中第一个元素作为标
9、准，将单链表中所有值小于第一个元素的结点均放在第一个元素结点之前，所有值大于第一个元素的结点均放在第一个元素结点之后（排除后续结点和第一个元素结点值相等的情况），补充完整程序并调试运行#include #include #include #define ElemType inttypedef struct Node ElemType data; struct Node * next;Node, *LinkList; int n;LinkList CreateFromTail() LinkList L; Node *r, *s; int c; int flag =1; L=(Node * )ma
10、lloc(sizeof(Node); L-next=NULL; r=L; n=0; while(flag) scanf(%d,&c); if(c!=-1) s=(Node*)malloc(sizeof(Node); s-data=c; r-next=s; r=s; n+; else flag=0; r-next=NULL; n+; return L; void ReverseList(LinkList L)/排除后续结点和首结点相等情况 Node *pi,*pj,*pindex; Node *temp; int len=sizeof(Node)-sizeof(Node *); int i,j;
11、 for(pi=L,i=0;inext) pindex=pi; for(pj=pi-next,j=i+1;jnext) if(pindex-data pj-data) pindex=pj; memcpy(&temp,pi,len); memcpy(pi,pindex,len); memcpy(pindex,&temp,len); void main() LinkList l; Node *p; printf(请输入数据(-1结束):); l = CreateFromTail(); printf(输入的单链表为:n); p = l-next; while(p!=NULL) printf(%dn,
12、p-data); p=p-next; ReverseList(l); printf(所有值小于第一个元素的结点均放在第一个元素结点之前n所有值大于第一个元素的结点均放在第一个元素结点之后n); printf(得到的单链表为:n); p = l-next; while(p!=NULL) printf(%dn,p-data); p=p-next; 5.P54实习题2，补充程序，完成调试和运行#include common.h#include stdio.htypedef struct Joseph /*结点类型定义*/ int index; int data; struct Joseph *nex
13、t;Joseph, *JosephList; void init_JosephList(JosephList *l)/*对单链表进行初始化*/ *l=(JosephList)malloc(sizeof(Joseph); (*l)-next=NULL;void CreateFromTail(JosephList L,int n) Joseph *r, *s; int c; int i; r=L; for(i=1;iindex=i; scanf(%d,&c); s-data=c; r-next=s; r=s; r-next=L-next; /构成约瑟夫环，注意不是L void GetJoseph(
14、JosephList l,int n,int m) JosephList p,q; int i; p=l; for(;) for(i=0;inext; printf(出列的人是第%d个人，密码是%dn,p-index,p-data); m=p-data; q-next=p-next; n-; if(n=0) break; void main() JosephList l; Joseph *p; int n,m,i; init_JosephList(&l); printf(输入参加约瑟夫环的人数:); scanf(%d,&n); printf(输入初始密码:); scanf(%d,&m); printf(用尾插法建立约瑟夫环,请输入链表数据!n); CreateFromTail(l,n); p = l-next; printf(约瑟夫环的人数以及对应密码分别是:n); for(i=1;iindex,p-data); p=p-next; GetJoseph(l,n,m);本次实验小结：
