作业1：线性表一、作业目的1．了解线性表的逻辑结构特性，以及这种特性在计算机的两种存储结构。

2．掌握线性表的顺序存储结构的定义及其C语言的实现。

3．掌握线性表的链式存储结构——单链表的定义及其C语言的实现。

4．掌握线性表在顺序存储结构即顺序表中的各种基本操作。

5．掌握线性表在链式存储结构——单链表的各种基本操作。

二、作业要求1.认真阅读和掌握本实验的程序。

2.上机运行本程序。

3.保存和打印出程序的运行结果，并结合程序进行分析。

4.按照对线性表和单链表的操作需要，重新改写主程序并运行，打印出文件清单和运行结果。

三、作业容1. 顺序表的操作请编制C程序，利用顺序存储方式来实现下列功能：根据键盘输入数据建立一个线性表，并输出该线性表；然后根据屏幕菜单的选择，可以进行表的创建，数据的插入删除并在插入和删除数据后再输出线性表；最后在屏幕菜单中选择0，即可结束程序的运行。

分析：当我们要在顺序表的第i个位置上插入一个元素时，必须先将线性表的第i个元素之后的所有元素一次后移一个位置，以便腾出一个位置，再把新元素插入到该位置。

当要删除第i个元素时，也只需将第i个元素之后的所有元素前移一个位置。

算法描述：对每个算法，都要写出算法的中文描述。

要求分别写出在第i 个（从1开始计数）结点前插入数据为x的结点、删除指定结点、创建一个线性表。

打印线性表等的算法描述。

2.单链表的操作请编制C程序，利用链式存储方式来实现线性表的创建、插入、删除和查找等操作。

具体地说，就是要根据键盘输入的数据建立一个单链表；然后根据屏幕菜单的选择，可以进行数据的插入或删除，并在插入或删除数据后，再输出单链表；最后在屏幕菜单中选择0，即可结束程序的运行。

算法描述：要求分别写出在带头结点的单链表中第i（从1开始计数）个位置之后插入元素、创建带头结点的单链表、在带头结点的单链表中删除第i个位置的元素、顺序输出单链表的容等的算法描述。

实验一：1.实验程序源代码#define TURE 1#define FALSE 0#define OK 1#define ERROR 0#define OVERFLOW -2#include<stdio.h>#include<stdlib.h>#define ML 1//线?性?表À¨ª#define TURE 1#define FALSE 0#define OK 1#define ERR 0typedef struct{int list[ML];int size;int MAXSIZE;}sqList;sqList *Init_List(sqList *L,int ms);void Disp_List(sqList *L);int LocateElem_List(sqList *L,int x);int Insert_List(sqList *L,int x,int mark);int Delete_List1(sqList *L,int item);int Delete_List2(sqList *L,int mark);sqList *Init_List(sqList *L,int ms){L=(sqList *)malloc(ms*sizeof(sqList));if(!L){printf("申¦¨º请?¨²存ä?空?间?出?错䨪\n");exit(OVERFLOW);}elseL->size=0;L->MAXSIZE=ms;return L;}void Disp_List(sqList *L){int i;for(i=0;i<L->size;i++)printf("%d",L->list[i]);printf("\n");}int LocateElem_List(sqList *L,int x){int i=0;for(i=0;i<=L->size;i++)if(L->list[i]==x)return i;if(i>L->size)return -1;}int Insert_List(sqList *L,int x,int mark){int i=1;if(L->size>=L->MAXSIZE)return -1;if(mark>0){for(i=L->size+1;i>=mark;i--)L->list[i+1]=L->list[i];L->list[i]=x;}else if(mark<0)L->list[L->size]=x;L->size++;return FALSE;}int Delete_List1(sqList *L,int item){int i,j;for(i=0;i<L->size;i++)if(item==L->list[i])break;if(i<L->size){for(j=i+1;j<L->size-1;j++)L->list[j]=L->list[j+1];L->size--;return i;}return FALSE;}int Delete_List2(sqList *L,int mark){int i,item;if(mark>0){item=L->list[mark];for(i=mark+1;i<L->size-1;i++)L->list[i]=L->list[i+1];L->size--;return i;}return FALSE;}void main(){int p,n,x=0;sqList a,*b;b=Init_List(&a,ML);printf("listaddr=%d\tsize=%d\tMaxSize=%d",b->list,b->size,b->MAXSIZE);while(1){printf("\n请?输º?入¨?值¦Ì，ê?0为a结¨¢束º?输º?入¨?：êo");scanf("%d",&x);if(!x) break;printf("\n请?输º?入¨?插?入¨?位?置?：êo\n");scanf("%d",&p);Insert_List(b,x,p);printf("\n线?性?表À¨ª为a：êo\n");Disp_List(b);}while(1){printf("\n请?输º?入¨?查¨¦找¨°值¦Ì，ê?输º?入¨?0结¨¢束º?查¨¦找¨°操¨´作Á¡Â：êo\n");scanf("%d",&x);if(!x) break;n=LocateElem_List(b,x);if(n<0) printf("\n没?找¨°到Ì?\n");elseprintf("\n又®?符¤?合?条¬?件t的Ì?值¦Ì，ê?位?置?为a：êo%d\n",n+1);}while(1){printf("\n请?输º?入¨?删¦?除y值¦Ì，ê?输º?入¨?0结¨¢束º?查¨¦找¨°操¨´作Á¡Â：êo\n");scanf("%d",&x);if(!x) break;n=Delete_List1(b,x);if(n<0)printf("\n没?找¨°到Ì?\n");else{printf("\n删¦?除y成¨¦功|，ê?线?性?表À¨ª为a:\n");Disp_List(b);}}while(1){printf("\n请?输º?入¨?删¦?除y值¦Ì位?置?，ê?输º?入¨?o结¨¢束º?查¨¦找¨°操¨´作Á¡Â:\n");scanf("%d",&p);if(!p) break;n=Delete_List2(b,p);if(p<0) printf("\n位?置?越?界?\n");else{printf("\n线?性?表À¨ª为a:\n");Disp_List(b);}}}2.实验运行图3.算法分析：（1）顺序表的初始化即是创造一个空表顺序表的初始化即构造一个空表，这对表是一个加工型的运算，因此，将L设为指针参数，首先动态分配存储空间，然后，将表中length指针置为0，表示表中没有数据元素。

算法如下：Status InitList_Sq(SqList *L){L->elem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));//分配存储空间if(!L->elem) exit(OVERFLOW); //存储分配失败L->length=0; //空表长度为0L->listsize=LIST_INIT_SIZE; //初始存储容量return OK;} // InitList_Sq此算法的时间复杂度为O(1)。