201310913232数据结构(2)

4

实验二 单链表基本操作的实现

一、实验学时： 2学时 二、实验目的

实现单链表的基本操作

三、实验内容

1. 单链表的建立、取指定元素、返回指定元素位置 2．单链表中插入新元素、删除指定元素操作的实现

四、主要仪器设备及耗材

硬件：计算机一台

软件：VC++ 6.0，MSDN2003或者以上版本

五、实验步骤

1. 分析问题 2. 写出算法 3. 编制程序 4. 上机调试 5. 分析结果

六、程序清单

#include #include typedef char ElemType;

typedef struct LNode /*定义单链表结点类型*/ { ElemType data; struct LNode *next; } LinkList;

void InitList(LinkList *&L) { L=(LinkList *)malloc(sizeof(LinkList)); /*创建头结点*/ L->next=NULL; }

void DestroyList(LinkList *&L) { LinkList *p=L,*q=p->next;

5

while (q!=NULL) { free(p); p=q; q=p->next; } free(p); }

int ListEmpty(LinkList *L) { return(L->next==NULL); }

int ListLength(LinkList *L) { LinkList *p=L;int i=0; while (p->next!=NULL) { i++; p=p->next; } return(i); }

void DispList(LinkList *L) { LinkList *p=L->next; while (p!=NULL) { printf(\,p->data); p=p->next; } printf(\); }

int GetElem(LinkList *L,int i,ElemType &e) { int j=0; LinkList *p=L; while (jnext; } if (p==NULL) return 0; else { e=p->data; return 1; } }

int ListInsert(LinkList *&L,int i,ElemType e) { int j=0; LinkList *p=L,*s; while (jnext; } if (p==NULL) /*未找到第i-1个结点*/ return 0; else /*找到第i-1个结点*p*/ { s=(LinkList *)malloc(sizeof(LinkList)); /*创建新结点*s*/ s->data=e; s->next=p->next; /*将*s插入到*p之后*/ p->next=s; return 1; } }

6

int ListDelete(LinkList *&L,int i,ElemType &e) { int j=0; LinkList *p=L,*q; while (jnext; } if (p==NULL) /*未找到第i-1个结点*/ return 0; else /*找到第i-1个结点*p*/ { q=p->next; /*q指向要删除的结点*/ p->next=q->next; /*从单链表中删除*q结点*/ free(q); /*释放*q结点*/ return 1; } }

void main() { LinkList *h; ElemType e; printf(\初始化单链表h\\n\); InitList(h); printf(\依次采用尾插法插入a,b,c,d,e元素\\n\); ListInsert(h,1,'a'); ListInsert(h,2,'b'); ListInsert(h,3,'c'); ListInsert(h,4,'d'); ListInsert(h,5,'e'); printf(\输出单链表h:\); DispList(h); printf(\单链表h长度=%d\\n\,ListLength(h)); printf(\单链表h为%s\\n\,(ListEmpty(h)?\空\:\非空\)); GetElem(h,3,e); printf(\单链表h的第个元素=%c\\n\,e); printf(\在第个元素位置上插入f元素\\n\); ListInsert(h,4,'f'); printf(\输出单链表h:\); DispList(h); printf(\删除h的第个元素\\n\); ListDelete(h,3,e); printf(\输出单链表h:\); DispList(h); printf(\释放单链表h\\n\); DestroyList(h); }

七、运行结果及分析

7

8