实验1线性表的基本操作

1、实验一 线性表的基本操作一、实验目的（1）掌握线性表顺序存储和链式存储的方法及基本运算的实现。（2）掌握将算法在VC+6.0语言环境下实现的过程。二、实验准备（1）复习线性表的定义，掌握顺序存储、链式存储的方法及操作。（2）复习C语言中指针与结构体的概念、定义方式。（3）掌握链表的C语言的实现。（4）实验的计算机中安装了Microsoft VC+ 6.0。三、实验内容顺序表1）首先创建一个顺序表：从键盘读入一组整数（长度小于等于20），按输入顺序放入顺序表，输入以1结束（注意1不放到顺序表内）；将创建好的顺序表元素依次输出到屏幕上。2）在已创建好的顺序表中插入一个元素：从键盘读入需插入的元素值

2、和插入位置，调用插入函数完成插入操作；然后将顺序表元素依次输出到屏幕上。3）在已创建好的顺序表中删除一个元素：从键盘读入欲删除的元素位置（序号），调用删除函数完成删除操作；然后将顺序表元素依次输出到屏幕上。算法提示：Ø 需求分析：1.功能 （1）建立一顺序表 （2）显示顺序表中每个元素 （3）在上述的顺序表中的指定位置插入指定的元素，并输出顺序表中所有数据。（4）在上述的顺序表中的指定位置删除指定的元素，并输出顺序表中所有数据。2输入要求从键盘输入顺序表中所有数据，输入以1结束（注意1不放到顺序表内）；需插入的数据元素的位置、值；要删除的数据元素的位置（序号）。3. 测试数据顺序表中

3、所有数据：15，26，58，27，9插入的数据元素的位置、值：1，28；6，28；0，28要删除的数据元素的位置：3Ø 概要设计：1. 数据结构：提示：相关常量和顺序表数据类型定义#define MAXNUM 20#define true 1#define false 0typedef struct int dataMAXNUM; int length;list_type; 2模块划分：a) 建立顺序表的createlist函数；b) 显示输出顺序中每个结点的数据的showlist函数；c) insertlist函数：插入函数。在已创建的顺序表中的指定位置插入指定数据，成功返回tru

4、e(1)，反之返回false(0)；做完插入操作后再输出顺序表中的所有数据。d) deletelist函数：删除函数。删除指定位置的元素，成功返回true(1)，反之返回false(0)；做完删除操作后再输出顺序表中的所有数据；e) 主函数main()，功能是给出测试数据值，建立测试数据值的顺序表，调用showlist函数、insertlist函数、deletelist函数实现问题要求。单向链表单向链表的基本操作，创建一个由6个节点组成的单向链表，显示链表中每个节点的数据，并且做增加、删除、查找节点以及计算单链表的长度等处理。Ø 需求分析：1.功能 （1）用尾插法创建一带头结点的由6

5、个节点组成的单向链表：从键盘读入一组整数，作为单链表中的元素，输入完第6个结点后结束；将创建好的单链表元素依次输出到屏幕上。 （2）显示链表中每个节点的数据 （3）从键盘输入一个数，查找在以上创建的单链表中是否存在该数；如果存在，显示它的位置，即第几个元素；如果不存在，给出相应提示如“No found node!”。 （4）在上述的单链表中的指定位置插入指定数据，并输出单链表中所有数据。（5）删除上述单链表中指定位置的结点，并输出单链表中所有数据。（6）求单链表的长度并输出。2输入要求先输入单链表中结点个数n，再输入单链表中所有数据，在单链表中需查找的数据，需插入的数据元素的位置、值，要删除的

6、数据元素的位置。3. 测试数据单链表中所有数据：12，23，56，21，8，10在单链表中需查找的数据：56；24插入的数据元素的位置、值：1，28；7，28；0，28 要删除的数据元素的位置：6Ø 概要设计：1. 算法思想：由于在操作过程中要进行插入、删除等操作，为运算方便，选用带头结点的单链表作数据元素的存储结构。对每个数据元素，由一个数据域和一个指针域组成，数据域放输入的数据值，指针域指向下一个结点。2. 数据结构： 单链表结点类型： typedef struct Liistnode int data;struct Listnode *next; NODE;3. 模块划分：a)

7、 用尾插法建立带头结点的单链表*CreateList函数；b) 显示链表中每个结点的数据PrintList函数；c) 从键盘输入一个数，查找单链表中是否存在该数FoundList函数；d) 在单链表中指定位置插入指定数据并输出单链表中所有数据InsertList函数；e) 删除单链表中指定位置的结点并输出单链表中所有数据DeleteList函数；f) 计算单链表的长度并在屏幕上输出LengthList函数；g) 主函数main(),功能是给出测试数据值，建立测试数据值的带头结点的单链表，调用PrintList函数、FoundList函数、InsertList函数、DeleteList函数、Le

8、ngthList函数实现问题要求。四、实验要求1 用C完成算法设计和程序设计并上机调试通过。2 撰写实验报告，提供实验结果和数据。五、源程序清单顺序表#include <stdio.h> #include <stdlib.h>#define MAXNUM 20#define true 1#define false 0typedef struct int dataMAXNUM; int length;list_type; /*提示：创建顺序表函数*/*create a list:input data from keyboard,end by -1*/void create

9、list(list_type *lp) int i, elem; lp->length=0; printf("nplease input datas of the listn"); for(i=0; i< MAXNUM; i+) scanf(" %d", &elem); if(elem= -1) break; lp->datai=elem; lp->length+; /*提示：遍历元素并依次输出函数*/void showlist(list_type *lp) int i; printf("nThese %d re

10、cords are:n", lp->length); if(lp->length<=0) printf("No data!n"); return; for(i=0; i<lp->length; i+) printf(" %d ", lp->datai); printf("nlength of the list is:%d", lp->length);/* 提示：插入函数，成功返回true，反之返回false。*/int insertlist(list_type *lp, int ne

11、w_elem, int i) int j; if(lp->length>=MAXNUM) printf("the list is full,can not insert."); return(false); if(i<1 | i>lp->length+1) printf("n%d is invalid value",i); return(false); for(j=lp->length-1; j>=i-1; j-) lp->dataj+1=lp->dataj; lp->datai-1=new_e

12、lem; lp->length+; return(true);/*提示：删除函数，成功返回true，反之返回false。*/int deletelist(list_type *lp, int i) int j; if(i<1 | i>lp->length) printf("elem not exist"); return(false); for(j=i; j<lp->length; j+) lp->dataj-1=lp->dataj; lp->length-; return(true);/*提示：主函数，按要求调用已编写

13、好的各函数*/void main( ) list_type list; int i, data; createlist(&list); showlist(&list); printf("ninsert:Enter i and data :n"); scanf("%d,%d", &i, &data); insertlist(&list, data, i); printf("nlist after insert:n"); showlist(&list); printf("ndele

14、te:Enter i:n"); scanf("%d", &i); deletelist(&list, i); printf("nlist after delete:n"); showlist(&list);单向链表#include <stdio.h>#include <stdlib.h>#include <malloc.h>#define NULL 0typedef struct ListNode int data;struct ListNode *next; NODE;/* 用尾插法

15、建立带头结点的单链表 */NODE *CreateList(int n) NODE *head, *p, *q;int num;int i=1;head=(NODE *)malloc(sizeof(NODE);head->next=NULL;p=head;while(i<=n)printf ("please input data:n"); scanf("%d",&num); q=(NODE *)malloc(sizeof(NODE);q->data=num; p->next=q; p=q;i+; p->next=NU

16、LL; return (head);/* 输出链表 */void PrintList(NODE *head ) NODE *p;p=head->next;printf ("Linear List: ");while (p!=NULL) printf ("%d ",p->data); p=p->next; printf ("n");/* 单链表查找节点 */int FoundList (NODE *head, int x ) NODE *p;int pos=1;p=head->next;while (p!=NUL

17、L)&&(p->data!=x) p=p->next; pos+; if (p!=NULL) return (pos); else return (0);/* 插入新结点（第i个位置上插入）*/void InsertList(NODE *head, int x, int i)NODE *p, *s;int j=0;p = head;while ( p!=NULL) && (j < i-1) p = p -> next; j+; if (p=NULL) | (j>i-1)printf( "nPostion Errorn&qu

18、ot;); else s = (NODE *)malloc(sizeof(NODE); s -> data = x; s -> next =NULL; s -> next = p -> next; p -> next = s; PrintList(head);/* 删除第i个结点*/void DeleteList(NODE *head, int i)NODE *p, *s;int j=0;p = head;while ( p-> next!=NULL) && (j < i-1) p = p -> next; j+; if (p-&

19、gt; next=NULL) | (j>i-1)printf( "nPostion Errorn"); else s=p-> next; p-> next=s-> next; free(s);PrintList(head);/* 求线性链表长度 */int LengthList (NODE *head ) int n;NODE *p;n=0; p=head->next;while (p!=NULL) p=p->next;n+;return (n);/* 主函数 */void main () NODE *head;int i,x,l,n;printf ("Enter node number for