数据结构实验指导书 - 线性表的操作

实验1 线性表的基本操作

一、实验目的

(1) 掌握线性表的逻辑特征；

(2) 掌握线性表顺序存储结构的特点，熟练掌握顺序表的基本运算； (3) 熟练掌握线性表的链式存储结构定义及基本操作； (4) 理解循环链表和双链表的特点和基本运算；

(5 )加深对顺序存储数据结构的理解和链式存储数据结构的理解，逐步培养解决实际问题的编程能力； 二、实验内容

1、创建有若干个元素（可以是整型数值）的顺序表，实现对顺序表的初始化，对已建立的顺序表插入操作、删除操作、遍历输出顺序表。

要求各个操作均以函数的形式实现，在主函数中调用各个函数实现以下操作：

（1）从键盘上依次输入21、18、30、75、42、56，创建顺序表，并输出顺序表中的各元素值。

（2）分别在单链表的第3个位置插入67，给出插入成功或失败的信息，并输出此时顺序表中的各元素值。

（3）删除顺序表中的第6个数据元素，给出删除成功或失败的信息，并输出此时顺序表中的各元素值。

（4）查找顺序表中是否有75这个元素，如果有返回该元素在顺序表中的位序。

2、创建有若干个元素（可以是整型数值）的单链表，实现对单链表的初始化，对已建立的顺序表插入操作、删除操作、查找操作、遍历输出单链表表。 要求各个操作均以函数的形式实现，在主函数中调用各个函数实现以下操作：

（1）从键盘上依次输入21、18、30、75、42、56，创建单链表，并输出单链表中的各元素值。

（2）分别在单链表的第4个位置，给出插入成功或失败的信息，并输出单链表中的各元素值。

（3）删除单链表中的第2个数据元素，给出删除成功或失败的信息，并输出单链表中的各元素值。

（4）查找顺序表中的第五个元素并输出该元素的值。 三、参考代码 (1) 顺序表的操作

#include #include

#define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0

#define OVERFLOW -2 typedef int Status;

#define INIT_SIZE 100 /*初始分配空间的大小*/

#define LISTINCREMENT 10 /*分配增量*/

typedef int ElemType; typedef struct{

ElemType *elem; int length; int listsize; }SqList;

/*ElemType elem[INIT_SIZE],注两者区别。存储空间的起始地址。*/ /*线性表中数据元素个数，即表长*/ /*线性表所申请的存储空间的大小*/

SqList CreateList_Sq(SqList L) /*创建一个空的线性表*/ {

L.elem=(ElemType *)malloc(INIT_SIZE*sizeof(ElemType)); if (!L.elem) exit(ERROR); L.length=0; /*表长为0*/ L.listsize=INIT_SIZE; /*申请的空间为初始大小*/ return L; }

Status InsertList_Sq(SqList *L, int i, ElemType e) /*在线性表的第i个位置前插入元素e*/ { int * newbase,*q,*p; int j;

if ((i<1)||(i>L->length+1)) {printf(\值不合法!\\n\ if (L->length>=L->listsize) /*当前空间已满，增加分配空间*/ {

newbase=(ElemType

*)realloc(L->elem,(L->listsize+LISTINCREMENT)*sizeof(ElemType)); if (!newbase) exit(ERROR); L->elem=newbase;

L->listsize= L->listsize+LISTINCREMENT; }

q=&(L->elem[i-1]);

for(p=&(L->elem[L->length-1]);p>=q;--p) *(p+1)=*p; *q=e;

L->length++; }

SqList DeleteList_Sq(SqList *L, int i, ElemType *e) /* 删除线性表中的第i个元素，并获得所删元素的值*/ { int j;

if ((i<1)||(i>L->length)) {printf(\值不合法!\\n\ *e=L->elem[i-1];

for(j=i;j<=L->length;j++)

L->elem[j-1]=L->elem[j]; L->length--; }

void Print_Sq(SqList L) /*遍历顺序线性表*/ { int i;

printf(\ for(i=0;i

if ((i+1)==0)

printf(\ else

printf(\ } }

int GetLength(SqList L) {

return L.length; }

int equal(ElemType e1,ElemType e2) /*判两个元素是否相等*/ {

if (e1==e2) return 1; else return 0; }

int LocateElem_Sq(SqList L,ElemType e, int (* compare)(ElemType e1,ElemType e2)) { int i; i=1;

while(i<=L.length && !(* compare)(L.elem[i-1],e)) i++; if (i<=L.length) return i; else return 0; }

void Getelem(SqList L,int i,ElemType *e) {

*e=L.elem[i-1]; }

int ListEmpty(SqList L) {

if (L.length==0) return 1; else return 0; }

void main() { int i;

SqList Lq; ElemType e;

Lq=CreateList_Sq(Lq); InsertList_Sq(&Lq,1,21); InsertList_Sq(&Lq,2,18); InsertList_Sq(&Lq,3,30); InsertList_Sq(&Lq,4,75); InsertList_Sq(&Lq,5,42); InsertList_Sq(&Lq,6,56); Print_Sq(Lq) ;

InsertList_Sq(&Lq,3,67); Print_Sq(Lq) ;

DeleteList_Sq(&Lq, 6, e); Print_Sq(Lq);

if (i=LocateElem_Sq(Lq,75,equal))

printf(\ else

printf(\ getch(); }

（2）单链表的操作

#include #include

typedef int ElemType;

/*定义结点类型*/ typedef struct Node {

ElemType data; /*单链表中的数据域 */ struct Node *next; /*单链表的指针域*/ }Node,*LinkedList;

/*单链表的初始化*/

LinkedList LinkedListInit() {

Node *L;

L = (Node *)malloc(sizeof(Node)); /*申请结点空间*/

if(L == NULL) /*判断是否有足够的内存空间*/ printf(\申请内存空间失败\\n\

L->next = NULL; /*将next设置为NULL,初始长度为0的单链表*/ return L; }

/*单链表的建立2，尾插法建立单链表*/

LinkedList LinkedListCreatT() {

Node *L,*r;

int x;

L = (Node *)malloc(sizeof(Node)); /*申请头结点空间 */ L->next = NULL; /*初始化一个空链表 */

r = L; /*r始终指向终端结点，开始时指向头结点*/

while(scanf(\ {

Node *p;

p = (Node *)malloc(sizeof(Node)); /*申请新的结点 */ p->data = x; /*结点数据域赋值 */

r->next = p; /*将结点插入到表头L-->|1|-->|2|-->NULL */ r = p; }

r->next = NULL;

return L; }

/*单链表的插入，在链表的第i个位置插入x的元素*/

LinkedList LinkedListInsert(LinkedList L,int i,ElemType x) {

Node *pre;

int tempi; /*pre为前驱结点*/ Node *p; pre = L;

for (tempi = 1; tempi < i; tempi++)

pre = pre->next; /*查找第i个位置的前驱结点*/ /*插入的结点为p*/ p = (Node *)malloc(sizeof(Node)); p->data = x;

p->next = pre->next; pre->next = p;

return L; }

/*单链表的删除，在链表中删除值为x的元素*/

LinkedList LinkedListDelete(LinkedList L,ElemType x) {

Node *p,*pre; /* pre为前驱结点，p为查找的结点*/ p = L->next;

while(p->data != x) /* 查找值为x的元素 */ {

pre = p; p = p->next; }

pre->next = p->next; /* 删除操作，将其前驱next指向其后继。*/ free(p); return L; }

int GetElem_L(LinkedList L, int i, ElemType e) {

/*L是带头结点的链表的头指针，以 e 返回第 i 个元素 */

Node *p; int j;

p = L->next; j = 1; /* p指向第一个结点，j为计数器 */

while (p && jnext; ++j; }

/* 顺指针向后查找，直到 p 指向第 i 个元素 */ /* 或 p 为空（P=最后一个元素内的指针域值）*/

if ( !p || j>i )

return 0; /* 第 i 个元素不存在 */

e = p->data; /* 取得第 i 个元素 return e; }

int main() { int i,e1;

ElemType x,e;

LinkedList list,start;

printf(\ list = LinkedListCreatT();

for(start = list->next; start != NULL; start = start->next) printf(\ printf(\

printf(\ scanf(\

printf(\ scanf(\

LinkedListInsert(list,i,x);

for(start = list->next; start != NULL; start = start->next) printf(\ printf(\

printf(\ scanf(\

LinkedListDelete(list,x);

for(start = list->next; start != NULL; start = start->next) */

printf(\ printf(\

e1=GetElem_L(list, 5, e) ;

printf(\ getch(); return 0; }

本文来源：https://www.bwwdw.com/article/p6lt.html