数据结构实验(链表操作)

1、 根据教材定义的链表结构，用C语言实现链表结构的创建、插

入、删除、查找等操作；

2、 利用上述链表操作实现如下程序：建立两个顺序表表示的集合

（集合中无重复的元素），并求这样的两个集合的并、交和差。 实验要求：

1、 用C语言建立自己的链表结构的程序库，实现链表的基本操作。 2、 对链表表示的集合，集合数据由用户从键盘输入（数据类型为

整型），建立相应的顺序表，且使得数据按从小到大的顺序存放，将两个集合的并、交和差的结果存储在一个新的线性表集合中，并输出。

3、 撰写实验报告并附上集合操作的程序和结果。

2014-3-14

程序代码：

#include

#include #include \"LinkList.h\" #include \"LinkList.c\"

/* 定义顺序表的元素类型。应根据需要修改 */ typedef int DataType;

struct Node { /* 单链表结点结构 */ DataType info;

struct Node * link; };

typedef struct Node * LinkList; /* 单链表类型 */

typedef struct Node * PNode; /* 结点指针类型 */

/* 创建一个带头结点的空链表 */

LinkList createNullList_link( void );

/* 判断带有头结点的单链表llist是否是空链表 */ int isNullList_link( LinkList llist) ;

/* 在llist带有头结点的单链表中找第一个值为x的结点存储位置 */ PNode locate_link(LinkList llist, DataType x );

/*在单链表中求p所指结点的前驱结点*/

PNode locatePre_link(LinkList llist, PNode p) ;

/* 在llist带头结点的单链表中,p所指结点后面插入元素x */ int insertPost_link(LinkList llist, PNode p, DataType x);

/*在带头结点的单链表llist中，p所指结点前面插入值为ｘ的新结点*/ int insertPre_link( LinkList llist, PNode p, DataType x );

/* 在llist带有头结点的单链表中删除第一个值为x的结点 */ int deleteV_link(LinkList llist, DataType x );

/*在带头结点的单链表llist中,删除p所指的结点*/ int deleteP_link(LinkList llist, PNode p ); void main( ) {

int n1=10,n2=5,i,j;

int a[10]={8,9,0,1,2,3,4,5,6,7}; int b[5]={2,4,8,6,10};

LinkList seta,setb,setc,setd,sete; PNode p,pa,pb;

seta=createNullList_link();//建立集合 setb=createNullList_link(); if (seta==NULL || setb==NULL){ printf(\"Out of space!!\\n\"); return; }

//按从小到大的顺序插入元素到集合a

for (i=0;ilink; //头结点

while(p!=NULL && p->info < a[i]) p=p->link; // 找到比a[i]大的第一个元素的位置 insertPre_link(seta,p,a[i]); /* 在p所指结点前面插入值为x的新结点 */ }

//按从小到大的顺序插入元素到集合b

for (i=0;ilink; //头结点

while(p!=NULL && p->info < b[i]) p=p->link; // 找到比a[i]大的第一个元素的位置 insertPre_link(setb,p,b[i]); /* 在p所指结点前面插入值为x的新结点 */ }

printf(\"the set a is :\\n\"); p=seta->link; while(p!=NULL ) {

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

printf(\" \\n\");

printf(\"the set b is :\\n\"); p=setb->link; while(p!=NULL ) {

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

printf(\" \\n\");

//并集 union

setc=createNullList_link(); p=setc;

pa=seta->link; pb=setb->link;

while(pa!=NULL && pb!=NULL){ //两个序列都没有结束时取小的先插入

if (pa->info < pb->info){

insertPost_link(setc,p,pa->info); p=p->link; pa=pa->link; }

else if(pa->info == pb->info){

insertPost_link(setc,p,pa->info); p=p->link; pa=pa->link; pb=pb->link; } else{

insertPost_link(setc,p,pb->info); p=p->link; pb=pb->link; } }

//扫尾处理，

while (pa!=NULL){

insertPost_link(setc,p,pa->info); p=p->link; pa=pa->link; }

while (pb!=NULL){

insertPost_link(setc,p,pb->info); p=p->link; pb=pb->link; } //输出

printf(\"the union set c is :\\n\"); p=setc->link; while(p!=NULL ) {

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

printf(\" \\n\");

//交集 intersection

setd=createNullList_link(); p=setd;

pa=seta->link; pb=setb->link;

while(pa!=NULL && pb!=NULL){

if(pa->info == pb->info){ //两个相同,插入 insertPost_link(setc,p,pa->info); p=p->link; pa=pa->link; pb=pb->link; }

else if (pa->info < pb->info) pa=pa->link; else

pb=pb->link; }

//输出

printf(\"the intersection set d is :\\n\"); p=setd->link;

while(p!=NULL ) {

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

printf(\" \\n\"); //差集

sete=createNullList_link(); p=sete;

pa=seta->link;

while(pa!=NULL){

if(locate_link(setb,pa->info)==NULL ){ insertPost_link(sete,p,pa->info); p=p->link; }

pa=pa->link; } //输出

printf(\"the subtract set e is :\\n\"); p=sete->link; while(p!=NULL ) {

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

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

LinkList createNullList_link( void ) /* 创建一个带头结点的空链表 */ {

LinkList llist = (LinkList)malloc( sizeof( struct Node ) );/*申请表头结点空间*/

if( llist != NULL ) llist->link = NULL;

else printf(\"Out of space! \\n\"); /*创建失败*/ return (llist); }

int isNullList_link( LinkList llist) {

/* 判断带有头结点的单链表llist是否是空链表 */ return (llist->link == NULL); }

PNode locate_link(LinkList llist, DataType x ) {

/* 在llist带有头结点的单链表中找第一个值为x的结点存储位置 */ PNode p;

if (llist==NULL) return(NULL); p = llist->link;

while( p != NULL && p->info != x ) p = p->link; return (p); }

int insertPost_link(LinkList llist, PNode p, DataType x) { /* 在llist带头结点的单链表中,p所指结点后面插入元素x */

PNode q = (PNode)malloc( sizeof( struct Node ) ); /* 申请新结点 */ if( q == NULL )

{printf( \"Out of space!!!\\n\" ); return(0); }

else { q->info = x; q->link = p->link; p->link = q; return(1); } }

int insertPre_link( LinkList llist, PNode p, DataType x ){

/*在带头结点的单链表llist中，p所指结点前面插入值为ｘ的新结点*/ PNode p1=locatePre_link(llist, p); return insertPost_link(llist, p1, x); }

PNode locatePre_link(LinkList llist, PNode p) { /*在单链表中求p所指结点的前驱结点*/ PNode p1;

if (llist==NULL) return(NULL); p1 = llist;

while( p1 != NULL && p1->link != p ) p1 = p1->link; return (p1); }

int deleteV_link( LinkList llist, DataType x )

/* 在llist带有头结点的单链表中删除第一个值为x的结点 */ {

PNode p, q; p = llist;

if(p==NULL) return(0);

while( p->link != NULL && p->link->info != x )

}

p = p->link; /*找值为x的结点的前驱结点的存储位置 */ if( p->link == NULL ) { /* 没找到值为x的结点 */ printf(\"Not exist!\\n \"); return(0); }

else {

q = p->link; /* 找到值为x的结点 */ p->link = q->link; /* 删除该结点 */ free( q ); return(1); }