《数据结构》（C语言版）严蔚敏著 - 数据结构实验指导(2)

3、阅读下面程序，在横线处填写函数的基本功能。并运行程序，写出结果。 #include #include #define ERROR 0 #define OK 1

typedef int ElemType; /*定义表元素的类型*/ typedef struct LNode{ /*线性表的单链表存储*/ ElemType data;

struct LNode *next; }LNode,*LinkList;

LinkList CreateList(int n); /* */ void PrintList(LinkList L); /*输出带头结点单链表的所有元素*/

int GetElem(LinkList L,int i,ElemType *e); /* */

LinkList CreateList(int n){ LNode *p,*q,*head; int i;

head=(LinkList)malloc(sizeof(LNode)); head->next=NULL; p=head;

for(i=0;i

q=(LinkList)malloc(sizeof(LNode)); printf(\

data %i:\ scanf(\输入元素值*/ q->next=NULL; /*结点指针域置空*/ p->next=q; /*新结点连在表末尾*/ p=q; }

return head; }/*CreateList*/

int InsertList(LinkList L, ElemType e, int i){ //Insert before ith element LNode* p = L; int j = 0;

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

if(!p || j>i) return ERROR;

LNode* s = (LinkList) malloc(sizeof(LNode)); s->data = e;

s->next = p->next;

6

p->next = s; return OK; }

int DeleteList(LinkList L, ElemType& e, int i){ //删除第i个元素，并由e返回其值 LNode* p = L; int j = 0;

while(p->next && jnext; j++; }

if(!(p->next) && j < i-1) return ERROR; LNode* q = p->next; p->next = q->next; e = q->data; free(q);

return OK; }

void PrintList(LinkList L){ LNode *p;

p=L->next; /*p指向单链表的第1个元素*/ while(p!=NULL){

printf(\ p=p->next; }

}/*PrintList*/

int GetElem(LinkList L,int i,ElemType *e){ LNode *p;int j=1; p=L->next;

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

if(!p||j>i)

return ERROR;

*e=p->data; return OK; }/*GetElem*/

int main(){

int n,i;ElemType e;

LinkList L=NULL; /*定义指向单链表的指针*/

7

printf(\输入单链表的元素个数*/ scanf(\ if(n>0){

printf(\ L=CreateList(n);

printf(\ PrintList(L);

printf(\ printf(\ scanf(\

if(GetElem(L,i,&e))

printf(\ else

printf(\ }else

printf(\ return 0; }

?

运行结果

?

算法分析

4、为第3题补充插入功能函数和删除功能函数。并在主函数中补充代码验证算法的正确性。 插入算法代码： ? 运行结果

8

?

算法分析

删除算法代码： ? 运行结果 ? 算法分析

以下为选做实验：

5、循环链表的应用（约瑟夫回环问题）

n个数据元素构成一个环，从环中任意位置开始计数，计到m将该元素从表中取出，重复上述过程，直至表中只剩下一个元素。

提示：用一个无头结点的循环单链表来实现n个元素的存储。 ? 算法代码

9

6、设一带头结点的单链表，设计算法将表中值相同的元素仅保留一个结点。

提示：指针p从链表的第一个元素开始，利用指针q从指针p位置开始向后搜索整个链表，删除与之值相同的元素；指针p继续指向下一个元素，开始下一轮的删除，直至p＝＝null为至，既完成了对整个链表元素的删除相同值。 ? 算法代码

四、实验小结

五、教师评语

10

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库《数据结构》（C语言版）严蔚敏著 - 数据结构实验指导(2)在线全文阅读。