数据结构第二次上机 第二章之单链表

xiaoxiao2021-02-28  6

实验题 2:实现单链表的各种基本运算的算法

2. 编写一个程序linklist.cpp,实现单链表的各种基本运算和整体建表运算(假设单链表的元素类型为char),并在此基础上设计一个程序exp2-2.cpp完成以下功能:

1)初始化单链表h

2)采用尾插法依次插入元素abcde

3)输出单链表h

4)输出单链表h长度;

5)判断单链表h是否为空;

6)输出单链表h的第3个元素;

7)输出元素a的位置;

8)在第4个元素位置上插入元素f

9)输出单链表h

10)删除h的第3个元素;

11)输出单链表h

12)释放单链表h

代码: 

#include<stdio.h> #include<stdlib.h> #include<malloc.h> typedef char ElemType; typedef struct LNode { ElemType data; struct LNode *next; }SqList; void InitList(SqList *&h) { h= (SqList *)malloc(sizeof(SqList)); //分配存放线性表的空间 h->next=NULL; //置空线性表长度为0 } void DestroyList(SqList *&h) //销毁线性表(DestroyList) { SqList *pre=h,*p=h->next; while(p!=NULL) { free(pre); pre=p; p=pre->next; } free(pre); } bool ListEmpty(SqList *h) //判断线性表是否为空表; { return(h->next==NULL); } int ListLength(SqList *h) //求线性表的长度,直接返回length 的长度即可; { int n=0; SqList *p=h; while(p->next!=NULL) { n++; p=p->next; } return(n); } void DispList(SqList *h) //输出线性表, { SqList *p=h->next; while(p!=NULL) { printf("%c ",p->data); p=p->next; } printf("\n"); } bool GetElem(SqList *h,int i,ElemType &e) { int j=0; SqList *p=h; if(i<=0) return false; while(j<i&&p!=NULL) { j++; p=p->next; } if(p==NULL) return false; else { e=p->data; return true; } } int LocateElem(SqList *h,ElemType e) { int i=1; SqList *p=h->next; while(p!=NULL&&p->data!=e) { p=p->next; i++; } if(p==NULL) return (0); else return (i); } void CreateListR(SqList *&h,ElemType a[],int n) { SqList *s,*r; h= (SqList *)malloc(sizeof(SqList)); r=h; for(int i=0;i<n;i++) { s=(SqList *)malloc(sizeof(SqList)); s->data=a[i]; r->next=s; r=s; } r->next=NULL; } bool ListInsert(SqList *h,int i,ElemType e) //插入数据元素; { int j=0; SqList *p=h,*s; if(i<=0) return false; while(j<i-1&&p!=NULL) { j++; p=p->next; } if(p==NULL) return false; else{ s=(SqList *)malloc(sizeof(SqList)); s->data=e; s->next=p->next; p->next=s; return true; } } bool ListDelete(SqList *&h,int i,ElemType &e) //删除数据元素; { int j=0; SqList *p=h,*q; if(i<=0) return false; while(j<i-1&&p!=NULL) { j++; p=p->next; } if(p==NULL) return false; else{ q=p->next; if(q==NULL) return false; e=q->data; p->next=q->next; free(q); return true; } } int main() { ElemType e,a[5]={'a','b','c','d','e'}; SqList *h; printf("单链表的计算功能如下:\n"); printf(" 1.初始化单链表h\n"); InitList(h); printf(" 2.依次采用尾插法插入a,b,c,d,e元素\n"); CreateListR(h,&a[0],5); printf(" 3.输出单链表h: "); DispList(h); printf(" 4.输出单链表h的长度= % d\n",ListLength(h)); printf(" 5.判断单链表h是否为空 %s\n",(ListEmpty(h)?"空":"非空")); // 叮叮! 三木比较也可以用在这里; GetElem(h,3,e); printf(" 6.输出单链表h的第3个元素 = % c\n",e); printf(" 7.输出单链表中元素a的位置 = %d\n",LocateElem(h,'a')); printf(" 8.在第4个元素位置上插入f元素\n"); ListInsert(h,4,'f'); printf(" 9.输出顺序表L: "); DispList(h); printf(" 10.删除L的第3个元素\n"); ListDelete(h,3,e); printf(" 11.输出顺序表L: "); DispList(h); printf(" 12.释放顺序表L\n"); DestroyList(h); return 0;

转载请注明原文地址: https://www.6miu.com/read-1100178.html

最新回复(0)