数据结构实验报告线性表及其应用.doc

数据结构实验报告（1）姓名： 张惠荣 学号： 6103115102 专业班级： 计算机科学与技术153实验目的：帮助学生掌握线性表的基本操作在顺序和链表这两种存储结构上的实现，尤以链表的操作和应用作为重点。问题描述：1、 问题描述：构造一个空的线性表L。2、 在线性表L的第i个元素之前插入新的元素e；3、 在线性表L中删除第i个元素，并用e返回其值。实验要求：1、 分别利用顺序和链表存储结构实现线性表的存储，并设计出在不同的存储结构中线性表的基本操作算法。2、 在实验过程中，对相同的操作在不同的存储结构下的时间复杂度和空间复杂度进行分析。算法分析：顺序结构算法：#define LIST_INIT_SIZE 100 /线性存储空间的初始分配量#define LISTINCREMENT 10 /线性表存储空间的分配增量typedef struct ElemType *elem;/存储空间基址int length; /当前长度int listsize;/当前分配的存储量Sqlist;Status InitList_Sq( SqList &L ) / 操作结果：构造一个空的顺序线性表 L.elem = (ElemType *) malloc( LIST_INIT_SIZE * sizeof( ElemType ) ); if ( !L.elem ) exit( OVERFLOW ); / 存储分配失败 L.length = 0; / 空表长度为0 L.listsize = LIST_INIT_SIZE; / 初始存储容量 return OK; /InitList_Sq Status ListInsert_Sq (SqList &L,int i ,ElemType e )/在顺序线性表L中第i个元素之前插入新的元素e，/i的合法值为1iListLength(L)+1,If(iListLength(L)+1) return ERROR;/i值不合法If（L.length=L.listsize）/当前存储空间已满，增加分配newbase=(ElemType*)realloc(L.elem, (L.listsize+LISTINCREATMENT)*sizeof(ElemType);if（！newbase）exit(OVERFLOW);/存储分配失败L.elem= newbase;/新基址Llistsize+=LISTINCREMENT;/增加存储容量q=&(L.elemi-1);/q为插入位置for(p=(&(L.elemL.length-1);p=q;-p)*(p+1)=*p;/插入位置及之后的元素后移*q=e;/插入e+L.length;/表长增1return OK;/ListInsert_SqStatus ListDelete_Sq (SqList & L,int i, ElemType e)/在顺序表L中删除第i个元素，并用e返回其值if(iListLength(L) return ERROR;/i值不合法for(p=&(L.elemi) ;pdata=e;LNode *p;p=L.next;int j=1;while(p!=NULL)&(ji-1)p=p.next;j+;p.next=q.next;q=p.next;return OK;/ Insert_LStatus Delete_L(LinkList &L,int i)/删除第i个元素p=L.next;int j=1;while(p!=NULL)&(ji-1)p=p.next;j+;q=p.next;p.next=q.next;e=q.data;free(q);return OK;/ Delete_L实验内容和过程：根据算法设计C语言程序，在visual stdio 上运行。顺序结构程序：#include#include #define LIST_INIT_SIZE 100#define LISTINCREMENT 10#define OVERFLOW 1#define OK 1#define ERROR 0typedef int ElemType;typedef int Status;typedef struct list ElemType *elem;/存储空间基址 int length;/当前长度 int listsize;/当前分配存储量 Sqlist;/构造一个空的线性表LStatus Initlist_Sq(Sqlist &L)L.elem = (ElemType*)malloc(LIST_INIT_SIZE * sizeof(ElemType);if (!L.elem) exit(OVERFLOW);L.length = 0;L.listsize = LIST_INIT_SIZE;return OK;/插入操作函数 Status insert_Sq(Sqlist &L, int i, int e)ElemType *p, *q, *newbase;if (iL.length + 1)return ERROR;if (L.length = L.listsize)/当前存储空间已满，增加分配 newbase = (ElemType*)realloc(L.elem, (L.listsize + LISTINCREMENT) * sizeof(ElemType);if (!newbase) exit(OVERFLOW);L.elem = newbase;L.listsize += LISTINCREMENT;q = &L.elemi - 1;for (p = (&L.elemL.length - 1); p = q; -p)*(p + 1) = *p;*q = e;+L.length;return OK;/删除操作函数 Status delete_Sq(Sqlist &L, int j)ElemType *p, *q;if (jL.length + 1)return ERROR;for (p = &(L.elemj - 1); p&(L.elemL.length); +p)*p = *(p + 1);-L.length;return OK;void show_Sq(Sqlist L)for (int i = 0; iL.length; i+)printf(%dt, L.elemi);int main()Sqlist L;int i;int a;/输入元素个数 printf(请输入要创建的元素个数:t);scanf(%d, &a);Initlist_Sq(L);L.length = a;printf(请输入线性表的元素:);getchar();for (i = 0; ia; i+)scanf(%d, &L.elemi);show_Sq(L);loop:printf(n请输入要进行的操作:n 1.插入n 2.删除n);int k;scanf(%d, &k);switch (k)case 1:int j, e;printf(请输入第i个元素之前插入e:t);getchar();scanf(%d%d, &i, &e);insert_Sq(L, i, e);show_Sq(L);break;case 2: printf(请输入要删除第i个元素:t);getchar();scanf(%d, &i);delete_Sq(L, i);show_Sq(L);break;default:printf(输入的数字不正确n);break;printf(n是否还要进行操作？(选择是按 1，选择否按 0):);scanf(%d, &i);if (i = 1)goto loop;return 0;链式结构程序：#include#include #define LEN sizeof(struct LNode)typedef int ElemType;typedef struct LNode ElemType data;/数据域 struct LNode *next;/指针域LNode;struct LNode *Init_L() /建立链表struct LNode *head;struct LNode *p, *q;head = (struct LNode*)malloc(LEN);if (!head) exit(0);/分配内存失败head-data = 0;head-next = NULL;return(head);struct LNode *creat(struct LNode *head)LNode *p, *q;int a;/输入元素个数 printf(请输入要创建的元素个数:t);scanf(%d, &a);getchar();int i;for (i = 0; idata);p-next = NULL;if (i = 0) q = p;head-next = p;elseq-next = p;q = p;return (head);struct LNode *Insert_L(struct LNode *head, int i, ElemType e)/在第i个元素之前插入e struct LNode *p, *q;q = (struct LNode*)malloc(LEN);/创建插入结点 if (!q) exit(0);/创建失败q-data = e;p = head-next;int j = 1;while (p != NULL) & (jnext;j+;q-next = p-next;p-next = q;return(head);struct LNode *Delete_L(struct LNode *head, int i)/删除第i个元素 struct LNode *p, *q;ElemType e;p = head-next;int j = 1;while (p != NULL) & (jnext;j+;q = p-next;p-next = q-next;e = q-data;free(q);return(head);void print(struct LNode *head)int i;LNode *p;p = head-next;while (p != NULL)printf(%dt, p-data);p = p-next;printf(n);int main()struct LNode *head;head = Init_L();creat(head);print(head);loop:printf(n请输入要进行的操作:n 1.插入n 2.删除n);int k;scanf(%d, &k);switch (k)case 1:int i; ElemType e;printf(请输入插入位置及元素（空格隔开）);scanf(%d%d, &i, &e);Insert_L(head, i, e);print(head);bre