2009级数据结构实验指导书(2)

数据结构实验指导书

int i ;

if (MergeQL(la,lb,&lc)) { printf(\

for(i=0;i<=lc.length ; i++) printf(\} }

3、单链表基本操作的实现

[问题描述]要在带头结点的单链表h中第i个数据元素之前插入一个数据元素

x ，首先需要在单链表中寻找到第i-1个结点并用指针p指示，然后申请一个由指针s 指示的结点空间，并置x为其数据域值，最后修改第i-1个结点，并使x结点的指针指向第i个结点，要在带头结点的单链表h中删除第i个结点，首先要计数寻找到第i个结点并使指针p指向其前驱第i-1个结点，然后删除第i个结点并释放被删除结点空间。

[基本要求]用链式存储结构实现存储

[实现提示]链式存储结构不是随机存储结构，即不能直接取到单链表中某个结

点，而要从单链表的头结点开始一个一个地计数寻找。

[程序实现]

# include # include typedef char DataType ;

typedef struct node{

DataType data; /*结点的数据域*/ struct node *next; /*结点的指针域*/ }ListNode;

void Init_List(ListNode **L) {

(*L)=(ListNode *)malloc(sizeof(ListNode));/*产生头结点*/ (*L)->next=NULL; }

int List_Length(ListNode *L ) {

int n=0;ListNode *p=L->next; while(p!=NULL) { n++;

p=p->next; }

return n; }

ListNode* GetNode(ListNode *L,int i) {

int j;

ListNode *p;

p=L;j=0; /*从头结点开始扫描*/

while(p->next&&j!=i) /*顺指针向后扫描,直到p->next为NULL或i=j为止*/

- 6 -

数据结构实验指导书

{

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

if(i==j)

return p; /*找到了第i个结点*/ else

return NULL; /*当i<0或i>0时,找不到第i个结点*/ }

void InsertList(ListNode *L,DataType x,int i) {

ListNode *p,*s;

p=GetNode(L,i-1); /*寻找第i-1个结点*/

if (p==NULL) /*i<1或i>n+1时插入位置i有错*/ { printf(\ return ; }

s=(ListNode *)malloc(sizeof(ListNode)); s->data=x;s->next=p->next;p->next=s; }

void DeleteList(ListNode *L ,int i) {

ListNode *p,*r;

p=GetNode(L,i-1); /*找到第i-1个结点*/

if (p==NULL||p->next==NULL) /*i<1或i>n时,删除位置错*/ { printf(\ return ; }

r=p->next; /*使r指向被删除的结点a*/ p->next=r->next; /*将ai从链上删除*/ free(r); }

/*使用头插法建立带头结点链表算法*/ ListNode * CreatListF(void) {

char ch;

ListNode *head=(ListNode *)malloc(sizeof(ListNode)); /*生成头结点*/ ListNode *s; /*工作指针*/ head->next=NULL;

ch=getchar(); /*读入第1个字符*/ while(ch!='\\n') {

s=(ListNode *)malloc(sizeof(ListNode)); /*生成新结点*/

s->data=ch; /*将读入的数据放入新结点的数据域中*/ s->next=head->next;

- 7 -

数据结构实验指导书

head->next=s;

ch=getchar(); /*读入下一字符*/ }

return head; }

/*使用尾插法建立带头结点链表算法*/ ListNode * CreatListR1(void) {

char ch;

ListNode *head=(ListNode *)malloc(sizeof(ListNode)); /*生成头结点*/ ListNode *s,*r; /*工作指针*/

r=head; /*尾指针初值也指向头结点*/ while((ch=getchar())!='\\n') {

s=(ListNode *)malloc(sizeof(ListNode)); s->data=ch; r->next=s; r=s; }

r->next=NULL; /*终端结点的指针域置空,或空表的头结点指针域置空*/ return head; }

/*复制链表A中的内容到表B中*/

void copy(ListNode *a, ListNode *b) {

ListNode *pa=a->next; ListNode *u; ListNode *rb=b; while(pa!=NULL) {

u=( ListNode *)malloc(sizeof(ListNode)); u->data=pa->data; rb->next=u; rb=u;

pa=pa->next; }

rb->next=NULL; }

/*输出带头结点的单链表*/

void DisplaySL(ListNode *la, char *comment) { ListNode *p ; p=la->next ;

if(p) printf(\ while(p) { printf(\ p=p->next; }

printf(\

- 8 -

数据结构实验指导书

}

/*主函数*/ main( )

{ ListNode *la ,*lb,*lc, *p ; int n,x,i;

printf(\用头插法建立链表la，请输入节点内容:\la=CreatListF();

DisplaySL(la,\新生成链la节点内容:\

printf(\链表la的长度: -\printf(\请输入要插入的元素: \scanf(\

printf(\请输入要插入的位置：\scanf(\InsertList(la,x,i);

DisplaySL(la,\插入后链la节点内容\printf(\请输入要删除元素的位置：\scanf(\DeleteList(la,i);

DisplaySL(la, \删除后链la节点内容\

printf(\用尾插法建立链表lb，请输入节点内容:\fflush(stdin); lb=CreatListR1();

DisplaySL(lb,\新生成链lb节点内容:\Init_List(&lc); copy(la,lc);

DisplaySL(lc,\复制生成的链lc节点内容:\}

4、有序单链表的合并

[问题描述] 已知单链表la和lb中的数据元素按非递减有序排列，将la和lb中的数据元素,合并为一个新的单链表lc,lc中的数据元素仍按非递减有序排列。

[基本要求] 不破坏la表和lb表的结构。 [程序实现]

# include #include #define NULL 0

typedef int DataType; typedef struct SLNode { DataType data;

struct SLNode * next; }slnodetype;

int MergeSL(slnodetype *la,slnodetype *lb,slnodetype **lc); int CreateSL(slnodetype *la,int n);

void DisplaySL(slnodetype *la , char * comment); main( )

{ slnodetype *la, *lb, *lc ,*p; int n,m;

la=(slnodetype *)malloc(sizeof(slnodetype)); la->next=NULL;

- 9 -

数据结构实验指导书

lb=(slnodetype *)malloc(sizeof(slnodetype)); lb->next=NULL;

lc=(slnodetype *)malloc(sizeof(slnodetype)); lc->next=NULL;

printf(\输入链la节点数:\scanf(\

printf(\输入链la 节点内容:\CreateSL(la,n);

DisplaySL(la,\链la 节点内容:\printf(\输入链lb节点数:\scanf(\

printf(\输入链lb节点内容:\CreateSL(lb,m);

DisplaySL(lb,\链lb 节点内容:\

if(MergeSL(la,lb,&lc)) DisplaySL(lc,\合成后的链lc:\getchar(); }

int MergeSL(slnodetype * la , slnodetype *lb,slnodetype * *lc) { slnodetype * pa, * pb, * pc; …… 此处隐藏：2039字，全部文档内容请下载后查看。喜欢就下载吧 ……