用C语言代码创建一个单链表,包含(1)创建链表(2)求表长(3)链表的查找...

发布网友 发布时间：2024-10-24 09:35

我来回答

共1个回答

热心网友 时间：2024-11-10 00:00

#include <stdio.h>
#include <malloc.h>
 
typedef int DataType;
 
typedef struct list {
    DataType data;
    struct list *next;
}*LinkList,*pNode;
 
LinkList GetEmptyList() {
    LinkList head = (pNode)malloc(sizeof(struct list));
head->data = 0;
    head->next = 0;
    return head;
}

// 创建链表
LinkList CreateList() {
int data;
pNode p;
LinkList head = GetEmptyList();
p = head;
printf("输入一个整数('q' to quit)：");
while(scanf("%d",&data) == 1) {
p->next = (pNode)malloc(sizeof(struct list));
p->next->data = data;
p = p->next;
printf("输入一个整数('q' to quit)：");
}
p->next = NULL;
return head;
}
 
// 将data插入到增序表head中，也可用来创建链表
void InsertNode(LinkList head, DataType data) {
pNode p,q = (pNode)malloc(sizeof(struct list));
    int flag = 1;
q->data = data;
    for(p = head; p->next && flag; p = p->next) {
        if(p->next->data > data) {
            q->next = p->next;
p->next = q;
flag = 0;
        }
    }
    if(flag) {
        p->next = q;
        q->next = NULL;
    }
}

LinkList CopyList(LinkList head) {
pNode p,q;
LinkList headcpy = q = GetEmptyList();
for(p = head->next; p; p = p->next) {
q->next = (pNode)malloc(sizeof(struct list));
q->next->data = p->data;
q = q->next;
}
q->next = NULL;
return headcpy;
}
 
// 合并 heada 和 headb 到 headc 
LinkList MergeList(LinkList heada, LinkList headb) {
pNode p,q,t;
int flag;
LinkList headc = CopyList(heada);
for(p = headb->next; p; p = p->next) {
t = (pNode)malloc(sizeof(struct list));
t->data = p->data;
flag = 1;
for(q = headc; q->next && flag; q = q->next) {
if(p->data < q->next->data) {
t->next = q->next;
q->next = t;
flag = 0;
}
}
if(flag) {
q->next = t;
t->next = NULL;
}
}
return headc;
}

// 在表中查找data，找到返回结点的地址，否则返回NULL
pNode Find(LinkList head,DataType data) {
pNode p = head->next;
while(p) {
if(p->data == data) return p;
p = p->next;
}
return NULL;
}

int GetLength(LinkList head) {
int len = 0;
pNode p = head->next;
while(p) {
++len;
p = p->next;
}
return len;
}
 
void ShowList(LinkList head) {
    pNode p;
    for(p = head->next; p; p = p->next)
        printf("%d ",p->data);
    printf("\n");
}
 
int main() {
    LinkList ListA,ListB,ListC;
DataType t;
 
    printf("创建ListA:\n");
    ListA = GetEmptyList();
    printf("输入一个整数('q' to quit):\n");
    while(scanf("%d",&t) == 1) {
        InsertNode(ListA,t);
        printf("输入一个整数('q' to quit):\n");
    }
    ShowList(ListA);
printf("ListA的长度：%d\n",GetLength(ListA));
 
    fflush(stdin); // 'q'退出后，键盘输入缓冲区中有残留数据
     
    printf("创建ListB:\n");
    ListB = GetEmptyList();
    printf("输入一个整数('q' to quit):\n");
    while(scanf("%d",&t) == 1) {
        InsertNode(ListB,t);
        printf("输入一个整数('q' to quit):\n");
    }
    ShowList(ListB);
printf("ListB的长度：%d\n",GetLength(ListB));
 
    printf("ListC = ListA ∪ ListB:\n");
    ListC = MergeList(ListA,ListB);
    ShowList(ListC);
printf("ListC的长度：%d\n",GetLength(ListC));
    return 0;
}