补充：顺序表复习

1、补充：顺序表复习顺序表的内容 一、基本逻辑概念（什么线性表）举例:表23 45 60 70 77 80 88 90 目标：查找，删除、插入 先解决的问题: 存储?学号学号姓名姓名年龄年龄是否退学是否退学1101050101王小二18N1101050103张三21N1101050405李四18Y1101050406刘小明20N1201050102杨升19N二、存储结构存储结构:(第一方法：顺序存储方法) 需要定义结构体数据类型(C语言):#define MAXSIZE 100typedef int elemtype; typedef struct elemtype dataMAXSIZE; in

2、t len; /*顺序表的长度*/ Sequenlist; 操作 结构类可以用来定义变量(分配存储空间用来存储线性表数据) 例如: Sequenlist R; 或Sequenlist *L; 作用：用于存储具体数据(线性表) 两者区别：第二需要初始化（why?）初始化Sequenlist *InitList(Sequenlist *L) L=( Sequenlist *)malloc(sizeof(Sequenlist); L-len=0; return(L); /*L为指向Sequenlist类型的指针变量*/向线性顺序空间输入数据/*顺序表输入数据*/void input(Sequenli

3、st *L)int i,x; i=0; printf(n Input data element ，1 as end:); / scanf(%d,&x); while(x!=-1) L-datai=x; i+; /*具体问题有所不同*/ if(i=MAXSIZE) printf(Table is overflow！); else scanf(%d,&x); /*具体问题有所不同*/ L-len=i;向线性顺序空间输出数据/*输出顺序表*/void output(Sequenlist *L) int i; printf(n Output element of Table：n); f

4、or(i=0;ilen;i+) printf(%d ,L-datai); /*具体问题有所不同*/*表中插入元素表中插入元素*/int InsItem (Sequenlist *L, int i, elemtype item)/*(*L).data0中存储表中存储表L的第一个数据元素的第一个数据元素a1*/ int j;if( (*L).len= MAXSIZE) /*表满，插入操作失败表满，插入操作失败*/ printf(The list is overflow.n); return 0; else if( (i(*L).len+1) ) /*插入位置设定不合适，插入操作失败插入位置设定不合

5、适，插入操作失败*/ printf(Position is not corrent.n); return 0; else for(j=(*L).len-1;j=i-1;j-) (*L).dataj+1=(*L).dataj; (*L).datai-1= item; (*L). len+; /*顺序表表长增顺序表表长增1*/ return 1; /*表中删除元素表中删除元素*/int DelItem(Sequenlist *L, int i)int j;if(*L).len=0) /*表空，删除操作失败表空，删除操作失败*/ printf(List is empty n); return 0;

6、else if( (i(*L).len) ) /*删除元素位置设定不合适，删除操作失败删除元素位置设定不合适，删除操作失败*/ printf(Delete item failn); return 0;else for ( j=i; jlen; if(j=0) /*表空，定位操作失败*/ printf(The sequenlist is empty); return 0; for(i=0;idatai=item ) return (i+1); printf(The item is not in this sequenlist); return 0; main() int item,i; Sequ

7、enlist *L; L=InitList(L); input(L); output(L); getch(); printf(n请输入你要插入元素值及插入位置，以空格间隔:); scanf(%d%d,&item,&i); if (InsItem (L, i, item)=1) printf(插入成功，结果为：); output(L); else printf(插入失败); printf(n请输入你要删除元素值的位置：); scanf(%d,&i); DelItem(L, i); output(L); printf(请输入你要查找的元素值：); scanf(%d,&

8、;item); if (LocItem(L,item)=0) printf(查找元素失败，不存在); else printf(元素所在位置为：%dn,LocItem(L,item);实现一个学生信息管理系统，实现一个学生信息管理系统，学生信息为如下表格，系统功学生信息为如下表格，系统功能要求对学生信息进行录入，能要求对学生信息进行录入，显示，插入一个新学生信息，显示，插入一个新学生信息，删除一个学生，并实现按学号删除一个学生，并实现按学号查找某学生信息。查找某学生信息。例：现有一学生学籍信息表，例：现有一学生学籍信息表，该表包含如下学生信息：学号该表包含如下学生信息：学号num、姓名、姓名na

9、me、年龄、年龄age、是否退学是否退学 LeaveSch。该信息。该信息表主要用于查询学生学籍信息，表主要用于查询学生学籍信息，如有新生入学，则在表尾加入如有新生入学，则在表尾加入新生信息，将其新生信息，将其LeavSch字段字段设为设为“N”：如有学生退学，则：如有学生退学，则将其将其LeavSch字段设为字段设为 “Y”。 学号学号姓名姓名年龄年龄是否退学是否退学1101050101王小二18N1101050103张三21N1101050405李四18Y1101050406刘小明20N1201050102杨升19N定义存储结构#define MAXSIZE 100typedef stru

10、ct Student char no10; char name20; int age; char leaveSch;Elemtype;typedef struct Elemtyp dataMAXSIZE; int len; /顺序表的长度Sequenlist;输入/*顺序表输入数据顺序表输入数据*/void input(Sequenlist *L)int i,x; char no10; char name20; int age; char leaveSch; i=0; printf(n 请输入数据元素的量请输入数据元素的量:); / scanf(%d,&x); while(x!=i)

11、/*具体问题有所不同具体问题有所不同*/ if(i=MAXSIZE) printf(Table is overflow！); else printf(n Input data element,以回车键间隔以回车键间隔:); scanf(%s,no); scanf(%s,name); /printf(n%s,name); scanf(%d,&age); fflush(stdin); scanf(%c,&leaveSch); strcpy(L-datai.no,no); strcpy(L-,name); L-datai.age=age; L-datai.leav

12、eSch=leaveSch; /*具体问题有所不同具体问题有所不同*/ i+; L-len=i;输出 /*输出顺序表*/ void output(Sequenlist *L) int i; printf(n Output element of Table：n); for(i=0;ilen;i+) printf(%s ,L-datai.no); /*具体问题有所不同*/ printf(%s ,L-); printf(%d ,L-datai.age); printf(%c ,L-datai.leaveSch); 例3 将顺序表（a1,a2,an）重新排列成以a1为界的两部分：a

13、1之前的值均比a1小，a1后面的值都比a1大”的算法，理解下面实验步骤三（3），认真体会算法与程序的区别。理解写算法与试验的区别 算法： 已知：输入，输出 步骤：输 入输出 算法思想：？实现算法 定义数据结构： 根据实验内容的描述设计数据结构 /*顺序表*/define MAXSIZE 100typedef int elemtype;typedef struct elemtype dataMAXSIZE; int len; /*顺序表数据元素的个数顺序表数据元素的个数*/Sequenlist;根据要求实现算法void part(SeqList *L) int i,j; elemtype x,y

14、; x=L-data0; for(i=1;ilen;i+) if(L-dataidatai; for(j=i-1;j=0;j-) L-dataj+1=L-dataj; L-data0=y; 实验测试算法 完整程序的组装:初始化，输入数据输出数据实验的算法主函数例：单链表应用例1 将顺序表（a1,a2,an）重新排列成以a1为界的两部分：a1之前的值均比a1小，a1后面的值都比a1大”的算法，理解下面实验步骤三（3），认真体会算法与程序的区别。理解写算法与试验的区别 算法： 已知：输入，输出 步骤：输 入输出 思想：？ 第一点数据与第二点后每一点比较，如果大于，则 移动该点到头结点的后面; 细化

15、：取到头结点、第一结点、取到第二结点，？单链表存储结构存储结构typedef int elemtype; /*定义新类型，类型名为elemtype*/typedef struct node elemtype data; /*数据域*/ struct node *next; /*指针域*/ linklist;Void part ( linklist *L) linklist *r, *p,*q; r=p=L-next; q=p-next;while(p!=NULL) if (r-dataq-data) p-next=q-next; q-next=L-next; L-next=q; p=q-next; e