链表实验报告

《数据结构》实验报告二

系别：嵌入式系统工程系 学号：11160400314 日期：2012年4月9日

班级：嵌入式11003班 姓名：孙立阔 指导教师：申华

一、上机实验的问题和要求：

单链表的查找、插入与删除。设计算法，实现线性结构上的单链表的产生以及元素的查找、插入与删除。具体实现要求：

1. 从键盘输入10个字符，产生不带表头的单链表，并输入结点值。

2. 从键盘输入1个字符，在单链表中查找该结点的位置。若找到，则显示“找到了”；否

则，则显示“找不到”。

3. 从键盘输入2个整数，一个表示欲插入的位置i，另一个表示欲插入的数值x，将x插

入在对应位置上，输出单链表所有结点值，观察输出结果。 4. 从键盘输入1个整数，表示欲删除结点的位置，输出单链表所有结点值，观察输出结果。 5. 将单链表中值重复的结点删除，使所得的结果表中个结点值均不相同，输出单链表所有

结点值，观察输出结果。

6. 删除其中所有数据值为偶数的结点，输出单链表所有结点值，观察输出结果。

7. （★）将单链表分解成两个单链表A和B，使A链表中含有原链表中序号为奇数的元

素，而B链表中含有原链表中序号为偶数的元素，且保持原来的相对顺序，分别输出单链表A和单链表B的所有结点值，观察输出结果。

二、程序设计的基本思想，原理和算法描述：

（包括程序的结构，数据结构，输入/输出设计，符号名说明等）

创建一个空的单链表，实现对单链表的查找，插入，删除的功能。

三、源程序及注释：

#define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 #define TRUE 1

1

#define FALSE 0 #define List_Init_Size 10 #define ListIncrement 2

typedef char ET; typedef ET * Ep; typedef int Status; typedef struct LNode{ ET data; struct LNode *next; }LNode, *LinkList; /*LinkList La,Lb,Lc;*/󰀀

#include \"stdio.h\" #include \"alloc.h\"

/*Display the linklist's elements. */ void printlk(LinkList L) { LinkList p; p=L->next; while (p) {

printf(\"%c -> \ p = p->next; }

printf(\"NULL\\n\"); }

/*Creat linklist from head node. */ void CreatList( LinkList *L,int n){ int i;

LinkList p,q; ET str[20],c;

p=(LinkList)malloc(sizeof(LNode)); p->next=NULL; *L = q = p;

printf(\"Please input the data : \"); for (i=n;i>0;i--) {

p=(LinkList)malloc(sizeof(LNode)); c = getche(); /*scanf(\"%c\ printf(\"\\n\\n\");

p->data = c;

p->next = q->next; q->next = p;

2

} }

/*Init the linklist. */ void Init(LinkList *L) { int n;

printf(\"Please input the number of the node : \"); scanf(\"%d\ CreatList(L,n); }

/* Get the value of element I; */

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

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

if(!p||j>i) return TRUE; *e=p->data; return FALSE; }

/*Insert a element after I */

int ListInsert(LinkList *L,int i,ET e) { /* Add your own codes. */ }

/*Delete the element I */

int ListDelete(LinkList *L,int i,ET *e) {

/* Add your own codes. */ }

int Insert(LinkList *L) { int i,flag; ET data;

printf(\"Please input the position : \"); scanf(\"%d\

printf(\"Please input the data : \");

data = getche(); /*scanf(\"%c\

3

flag = ListInsert(L,i,data); return flag; }

Status Delete(LinkList *L) { int i,flag; ET e;

printf(\"Please input the number : \"); scanf(\"%d\

flag = ListDelete(L,i,&e);

printf(\"Deleted element is %c\\n\ return flag; }

/*Find the element's position. */ int LocateElem(LinkList L,ET e) { int i=0; LinkList p; p = L->next; while (p) { i++;

if (p->data == e) return i; }

return 0; }

/*Add the Lb after the La. */

void Union( LinkList *La ,LinkList *Lb){ LinkList pa,pb;

/* Add your own codes. */ }

/*Merge two sequence into one,don't change any elements in these two link lists. Join two sequence to one. */

void MergeList(LinkList *L1,LinkList *L2,LinkList *L3) { LinkList pa,pb,pc;

/* Add your own codes. */ }

/*List the Menu*/ void MenuList() {

printf(\"\\n\\n\\n==========================\\n\");

4

printf(\" 1 ******* Insert LA\\n\"); printf(\" 2 ******* Insert LB\\n\"); printf(\" 3 ******* Delete LA\\n\"); printf(\" 4 ******* Delete LB\\n\");

printf(\" 5 ******* Union LA and LB\\n\");

printf(\" 6 ******* Merge LA and LB to LC\\n\"); printf(\" 7 ******* print LinkList\\n\"); printf(\" 8 ******* Exit\\n\");

printf(\"==========================\\n\"); }

/*Select the menu */

void MenuSelect(LinkList *La,LinkList *Lb){ int select,done=1; LinkList Lc;

while (done) { MenuList( );

printf(\"input the operating code : \"); scanf(\"%d\ switch(select){ case 1: Insert(La);break; case 2: Insert(Lb);break; case 3: Delete(La);break; case 4: Delete(Lb);break; case 5: Union(La,Lb);break; case 6: MergeList(La,Lb,&Lc); printf(\"LC: \");printlk(Lc); break; case 7: printf(\"LA: \");printlk(*La); printf(\"LB: \");printlk(*Lb); break; case 8: done=0;break; default: printf(\" ERROR\\n\"); } } }

main( ){

LinkList La,Lb; printf(\"LA \"); Init(&La) ; printlk(La);

printf(\"LB \");

5

Init(&Lb) ; printlk(Lb);

MenuSelect(&La,&Lb); }

调试后的代码：

#include #include typedef int DataType; typedef struct LinkList {

int data;

struct LinkList *next; }LinkList;

void PrintList(LinkList *h); LinkList* InitList();

void InsList(LinkList *h,int i,DataType x); void LocList(LinkList *h,int i); void DelList(LinkList *h,int i);

void main() {

int i,n,x; LinkList *h; h=InitList(); PrintList(h);

printf(\"\\n===========\\n\"); printf(\"0------EXIT\\n\"); printf(\"1------INSERT\\n\"); printf(\"2------DELERT\\n\"); printf(\"3------LOCERT\\n\");

printf(\"\\n===========\\n\\n\\n\");

while(1) {

printf(\"\\nSelect\\n\"); scanf(\"%d\ switch(n) {

case 0:

6

exit(0); break; case 1:

printf(\"please input the position:\\n\"); scanf(\"%d\

printf(\"please input the data:\\n\"); scanf(\"%d\ InsList(h,n,x); PrintList(h); break; case 2:

printf(\"please input you want to delete position:\\n\"); scanf(\"%d\ DelList(h,i); PrintList(h); break; case 3:

printf(\"please input you want to search position:\\n\"); scanf(\"%d\ LocList(h,i); PrintList(h); break; default :

printf(\"error\\n\"); break; } } }

LinkList* InitList() {

LinkList *h,*s,*r; int a,c,i;

h=(LinkList*)malloc(sizeof(LinkList)); h->next=NULL; r=h;

printf(\"please input some link's length:\"); scanf(\"%d\ for(i=0;iscanf(\"%d\

7

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

s->next=r->next; r->next=s;

r=r->next; }

return h; }

void InsList(LinkList *h,int i,DataType x) {

LinkList *s,*p; int j=1; p=h;

s=(LinkList*)malloc(sizeof(LinkList)); for(j=1;jnext; if(p==NULL)

printf(\"error!\\n\"); else {

s->data=x;

s->next=p->next; p->next=s; } }

void DelList(LinkList *h,int i) {

LinkList *p,*q; int j=1; p=h->next; q=p->next;

while(j!=i-1 && q!=NULL) {

p=p->next; q=q->next; j++; }

if(q==NULL)

printf(\"error!\\n\"); else

8

{

p->next=q->next; free(q); } }

void LocList(LinkList *h,int i) {

LinkList *p; int j=1; p=h->next;

while(p!=NULL) {

if(p->data==i) {

printf(\"position is %d\\n\ break; }

p=p->next; j++; }

if(p==NULL)

printf(\"NO this data in the link\\n\"); }

void PrintList(LinkList*h) {

LinkList *p; p=h->next;

while(p!=NULL) {

printf(\" %d ->\ p=p->next; } }

9

四、运行输出结果：

五、调试和运行程序过程中产生的问题及采取的措施：

问题：子函数和主函数前后的调用出现问题，指针的调用不是太明白。 措施：根据编译器提示的错误逐个检查子函数前后的变量，以及寻求同学的帮助。

10

六、对算法的程序的讨论、分析，改进设想，其它经验教训：

看一段代码和亲自动手编写一套程序差别太大了，所以以后还

要多亲手上机操作，还有对指针的调用方便还很欠缺，要多学习。

七、对实验方式、组织、设备、题目的意见和建议：

希望老师以后可以给我们多些自己动手实践的机会，可以在课堂上多让我们动手去上机操作，老师带领我们完成主要部分，或给一些提示指导。

11