链表的c语言实现（三）

二、单链表枯基的基本运算

建立了一个单链表之后，如果要进行一些如插入、删除等 *** 作该怎么办？所以还须掌握一些单链表的基本算法，来实现这些 *** 作。单链表的基本运算包括：查找、插入和删除。下面我们就一一介绍这三种基本运算的算法，并结合我们建立单链表的例子写出相应的程序。

1、查找

对单链表进行查找的思路为：对单链表的结点依次扫描，检测其数据域是否是我们所要查好的值，若是返回该结点的指针，否则返回NULL。

因为在单链表的链域中包含了后继结点的存储地址，所以当我们实现的时候，只要知道该单链表的头指针，即可依次对每个结点的数据域进行检测。

以下是应用查找算法的一个例州败笑子：

#include

#include

#include /*包含一些字符串处理函数的头文件*/

#define N 10

typedef struct node

{

char name[20]

struct node *link

}stud

stud * creat(int n) /*建立链表的函数*/

{

stud *p,*h,*s

int i

if((h=(stud *)malloc(sizeof(stud)))==NULL)

{

printf("不能分配内存空间!")

exit(0)

}

h->name[0]='\0'

h->link=NULL

p=h

for(i=0i<ni ) {

if((s= (stud *) malloc(sizeof(stud)))==NULL)

{

printf("不能分配内存空间!")

exit(0)

}

p->link=s

printf("请输入第%d个人的姓名册含",i 1)

scanf("%s",s->name)

s->link=NULL

p=s

}

return(h)

}

stud * search(stud *h,char *x) /*查找链表的函数，其中h指针是链表的表头指针，x指针是要查找的人的姓名*/

{

stud *p/*当前指针，指向要与所查找的姓名比较的结点*/

char *y/*保存结点数据域内姓名的指针*/

p=h->link

while(p!=NULL)

{

y=p->name

if(strcmp(y,x)==0) /*把数据域里的姓名与所要查找的姓名比较，若相同则返回0，即条件成立*/

return(p)/*返回与所要查找结点的地址*/

else p=p->link

}

if(p==NULL)

printf("没有查找到该数据!")

}

main()

{

int number

char fullname[20]

stud *head,*searchpoint/*head是表头指针，searchpoint是保存符合条件的结点地址的指针*/

number=N

head=creat(number)

printf("请输入你要查找的人的姓名:")

scanf("%s",fullname)

searchpoint=search(head,fullname)/*调用查找函数，并把结果赋给searchpoint指针*/

}

#include <stdio.h>  隐吵

#include <malloc.h>  

#include <stdlib.h>  

  

typedef struct Node  

{  

    int data  

    struct Node *next  

}Node,*LinkList  

  

bool InitList(LinkList *L) //链表的初始化  

bool ListInsert(LinkList L,int pos,int e) //在pos位置插入e值  

bool ListTraverse(LinkList L) //遍历输出链表的值  

bool GetElem(LinkList L,int pos,int *e) //将链表第pos个位置的值赋给 e  

bool comp(int c1,int c2) //数据元素判定函数  

int LocateElem( LinkList L,int e,bool (*comper)(int,int) ) //返回L中第1个与e满足关系compare()的数据元素的位序  

int ListLength(LinkList L) //求L中数据元素的个数  

bool ListDelete(LinkList L,int pos,int *e) //删除第pos个元素，并由e返回其值  

 

  

int main()  

{  

    LinkList L   

    int e, e0  

    int j, k  

    InitList(&L) //链表的初皮好始化   

    for(j = 1 j <= 5 j++)  

        ListInsert(L,1,j)  //插入  

    printf("在L的表头依次插入1~5后：L = ")  

    ListTraverse(L) //遍历  

     

       

  

    for(j = 1 j <= 10 j++)  

        ListInsert(L,j,j)  

    printf("在L表的表尾依次插入1-10后 L = ")  

    ListTraverse(L)  

    GetElem(L,4,&e) //得到链表第4个数据  

    printf("第4个元素的值为：%d\n",e)  

  

    for(j = 0 j <= 2 j++)  

    {  

    灶握侍    k = LocateElem(L,j,comp)  

        if(k)  

            printf("第%d个元素的值为%d\n",k,j)  

        else  

            printf("没有值为%d的元素\n")  

    }  

  

      

  

    k = ListLength(L) //k为表长  

      

    for(j = k+1 j >= k j--)  

    {  

          

        if( ListDelete(L,j,&e) )  //删除第j个元素  

        {  

          

            printf("删除第%d个元素为：%d\n",j,e)  

        }  

        else  

            printf("删除第%d个元素失败\n",j)  

    }  

    printf("依次输出L的元素：")  

    ListTraverse(L)  

  

    

    return 0  

}  

  

bool InitList(LinkList *L)  

{  

    *L = (LinkList)malloc(sizeof(Node))  

    if(*L == NULL)  

    {  

        printf("内存分配失败 程序终止！\n")  

        exit(-1)  

    }  

    (*L)->next = NULL //指针域为空  

    return true  

}  

  

bool ListInsert(LinkList L,int pos,int e) //在pos位置插入e值  

{  

    int j = 0  

    LinkList p = L, s  

    while(p != NULL && j < pos - 1)  

    {  

        p = p->next  

        j++  

    }  

    if(p == NULL || j > pos - 1)  

        return false  

    s = (LinkList)malloc(sizeof(Node)) //生成新节点  

    s->data = e  

    s->next = p->next  

    p->next = s  

    return true  

}  

  

bool ListTraverse(LinkList L) //遍历输出链表的值  

{  

    LinkList p = L->next  

    while(p != NULL)  

    {  

        printf("%d ",p->data)  

        p = p->next  

    }  

    printf("\n")  

    return true  

}  

  

bool GetElem(LinkList L,int pos,int *e) //将链表第pos个位置的值赋给 e  

{  

    int j = 1 //j 为计数器  

    LinkList p = L->next //p指向第一个结点  

    while(p != NULL && j < pos) //顺指针向后查找，直到p指向第pos个元素 或 p 为空  

    {  

        p = p->next  

        j++  

    }  

    if(p == NULL || j > pos)  

        return false  

    *e = p->data  

    return true  

}  

  

bool comp(int c1,int c2) //数据元素判定函数  

{  

    if(c1 == c2)  

        return true  

    else  

        return false  

}  

  

int LocateElem( LinkList L,int e,bool (*compare)(int,int) )  

{  

    int i= 0  

    LinkList p = L->next  

    while(p != NULL)  

    {  

        i++  

        if( compare(p->data,e) )  

            return i  

        p = p->next  

    }  

    return 0  

}  

  

int ListLength(LinkList L) //求L中数据元素的个数  

{  

    int i = 0  

    LinkList p = L->next //p 指向第一个结点  

    while(p != NULL) //没有到表尾  

    {  

        i++  

        p = p->next  

    }  

    return i  

}  

  

bool ListDelete(LinkList L,int pos,int *e) //删除第pos个元素，并由e返回其值  

{  

    int j = 0  

    LinkList p = L, q  

    while(p->next != NULL && j < pos - 1) //寻找第i个结点，并令p指向其前驱  

    {  

        p = p->next  

        j++  

    }  

    if(p->next == NULL || j > pos - 1)  

        return false  

    q = p->next //以下几行删除并释放结点  

    p->next = q->next  

    *e = q->data  

    free(q)  

    return true  

}

这个是我们数据结构巧乎上机实验的链表问题，

#include<stdio.h>

#include<malloc.h>

#define LEN sizeof(LinkNode)

typedef int Datatype

typedef int Status

typedef struct LinkNode{

Datatype data

struct LinkNode *next

} LinkNode,*LinkList

typedef struct OrderedList

{

LinkNode *head,*tail

int Listsize

} OrderedList//有序磨宽岩循环链表的头节点head,尾接接节点 tail及长度Listsize

Status InitList(OrderedList *List)//生成循环链表头节点

{

List->tail=List->head=(LinkList)malloc(LEN)

if(List->head==NULL)

return 0

else

{

List->head->next=List->tail

List->tail->next=List->head

List->Listsize=0

return 1

}

}

void OrderedInsert(OrderedList *List,Datatype data)//每瞎御调用一次有序插入data形成有序的(从小到大)的链表

{LinkNode *p ,*q

if(List->head==List->tail->next)

{

p=(LinkNode*)malloc(LEN)

p->data = data

List->head->next=p

p->next=List->tail

List->Listsize++

}

else

{

p=List->head->next

q = List->head

while(p->data<data&&p!=List->tail)

{

q = p

p=p->next

}

if(p->data==data)

{printf("YOu have input the same datas %d\n\t YOu should input another data \n",data)

scanf("%d",&data)

OrderedInsert(List,data)

}

else

{

p=(LinkNode*)malloc(LEN)

p->data = data

p->next = q->next

q->next = p

List->Listsize++

}

}

}

void Creatset(OrderedList *List)//多次调用OrderedInsert()生成有序链表即集合List

{

Datatype data

int setsize , i=0

printf("Please input the setsize you want to creat:\n")

scanf("%d",&setsize)

InitList(List)

if(setsize==0)

printf("You needen't input any data\n")

else if(setsize==1)

printf("Please input a single data\n")

else

printf("Please input %d different datas\n",setsize)

while(i<setsize||setsize>List->Listsize)//当循环次数i小于setsize或者集合内实际元素数List.Listsize小于setsize时一直循环下去

{

scanf("%d",&data)

OrderedInsert(List,data)

i++

}

}

void Append(OrderedList *List,Datatype data)//在循环链表的最后面追加 一个data

{

LinkNode *p

p=(LinkNode*)malloc(LEN)

p->data=data

List->tail=List->tail->next=p

List->tail->next=List->head

List->Listsize+=1

}

void MergeList(OrderedList La,OrderedList Lb,OrderedList *Lc)//有序循环链表ListLa,ListLb求并集生成ListLc

{

LinkList Pa,Pb

Pa=La.head->nextPb=Lb.head->next

while(Pa!=La.tail&&Pb!=Lb.tail)

{

if(Pa->data<=Pb->data)

{

Append(Lc,Pa->data)

Pa=Pa->next

}

else {

Append(Lc,Pb->data)Pb=Pb->next

}

}

while(Pa!=La.tail)

{ Append( Lc,Pa->data)Pa=Pa->next}

while(Pb!=Lb.tail)

{ Append(Lc,Pb->data)Pb=Pb->next}

}

void Print(OrderedList List)

{

LinkNode *p

p=List.head->next

if(p->next==List.head)

printf("No Elem\n")

while(p!=List.head)

{ printf("%5d",p->data)p=p->next }

printf("\n")

}

void main()

{

OrderedList ListLa,ListLb,ListLc

Creatset(&ListLa)

Creatset(&ListLb)

InitList(&ListLc)

MergeList(ListLa,ListLb,&ListLc)

printf("The orgnial list ListLa,ListLb:\n")

Print(ListLa)

Print(ListLb)

printf("The Merge list ListLc\n")

Print(ListLc)

}

---