数据结构之单链表

[jyzwf]

单链表是数据结构里的常用结构，操作有：

1. initList 初始化列表
2. ListEmpty 判断链表是否为空
3. Get 按序号查找操作
4. LocateEle 按内容查找
5. LocatePos 定位操作
6. insertList 插入操作
7. deleteList 删除操作
8. ListLength 求表长度
9. destoryList 销毁链表

主文件

#include <stdio.h>
#include <stdlib.h>


#include "linkList.h"
void delEle(LinkList A,LinkList B);

int main()
{
    int i;
    int a[] = {2,3,6,7,9,14,56,45,65,67};
    int b[] = {3,4,7,11,34,54,45,67};

    LinkList A,B;
    ListNode *p;

    /*
       initList(A);这样就传对应于linkList.h中注释的那个部分结果就会崩溃，，为什么？
    */
    initList(&A);
    initList(&B);

    //
    for(i=1;i<=sizeof(a)/sizeof(a[0]);i++)
    {
           if(insertList(A,i,a[i-1])==0){
              printf("插入失败");
              return 0;
           }
    }

    for(i=1;i<=sizeof(b)/sizeof(b[0]);i++)
    {
           if(insertList(B,i,b[i-1])==0){
              printf("插入失败");
              return 0;
           }
    }


    printf("单链表A中的元素有%d个:\n",ListLength(A));

    for(i=1;i<=ListLength(A);i++)
    {
           p= Get(A,i);
           if(p)
              printf("%4d",p->data);
    }

    printf("\n");


    printf("单链表B中的元素有%d个:\n",ListLength(B));

    for(i=1;i<=ListLength(B);i++)
    {
           p= Get(B,i);
           if(p)
              printf("%4d",p->data);
    }

    printf("\n");

    delEle(A,B);
    printf("将在A中出现的B元素删除后长度是%d：\n",ListLength(A));
    for(i=1;i<=ListLength(A);i++)
    {
           p= Get(A,i);
           if(p)
              printf("%4d",p->data);
    }

    return 0;
}

void delEle(LinkList A,LinkList B)
{
       int i ,pos;
       int e;
       ListNode *p;

       for(i=0;i<ListLength(B);i++)
       {
              p=Get(B,i);
              if(p){
                     pos = LocatePos(A,p->data);
                     if(pos>0)
                            deleteList(A,pos,e);
              }
       }
}

头文件

#ifndef LINKLIST_H_INCLUDED
#define LINKLIST_H_INCLUDED

struct Node
{
       int data;
       struct Node *next;
};


typedef struct Node ListNode,*LinkList;

// 初始化链表
void initList (LinkList *head)    
// head是指向指针变量A的指针变量，所以head里面存的是A的地址，*head 就是main 里面的 A
{
        if((*head = (LinkList)malloc(sizeof(ListNode)))==NULL)
       {
              exit(-1);
       }
       (*head)->next = NULL;
}

/*
void initList (LinkList head)      // 这样就会报错
{
        if((head = (LinkList)malloc(sizeof(ListNode)))==NULL)
       {
              exit(-1);
       }
       head->next = NULL;
}*/

// 判断链表是否为空
int ListEmpty(LinkList head)
{
       if(head->next==NULL)
              return 1;
       return 0;
}

// 按序号查找操作
ListNode *Get(LinkList head,int i)
{
       ListNode *p;
       int j=0;

       if(ListEmpty(head))
              return NULL;

       if(i<1)
              return NULL;

       p = head;

       while(p->next!=NULL&& j<i)
       {
              p = p->next;
              j++;
       }

       if(j==i)
              return p;
       else
              return NULL;
}

// 按内容查找
ListNode *LocateEle(LinkList head,int i)
{
       ListNode *p;
       p = head->next;
       while(p)
       {
              if(p->data !=i){
                     p = p->next;
              }else
              {
                     break;
              }
       }

       return p ;
}


// 定位操作
int LocatePos(LinkList head,int i)
{
       int j=1;
       ListNode *p;
       p = head->next;

       while(p)
              if(p->data==i){
                     return j;
              }else{
                     p = p->next;
                     j++;
              }

       if(!p)
              return 0;

}


// 插入操作
int insertList(LinkList head,int i,int e)
{
       ListNode *p,*pre;    // p 是新生成的节点，pre 是要插入位置的前一个节点
       int j=0;
       pre = head;

       while(pre->next!=NULL && j<i-1){
             pre = pre->next;
             j++;
       }

       if(j!=i-1){
              printf("插入位置错误");
              return 0;
       }

       p = (LinkList) malloc(sizeof(ListNode));
       p->data = e;
       p->next = pre->next;
       pre->next = p;
       return 1;
}


// 删除操作
int deleteList(LinkList head,int i,int e)
{
       LinkList p ,pre;
       int j=0;
       pre = head;
       while(pre->next!=NULL&&pre->next->next!=NULL&&j<i-1)
       {
              pre= pre->next;
              j++;
       }

       if(j!=i-1){
              printf("删除位置错误");
              return 0;
       }

       p = pre->next;
       e = p->data;

       pre->next=p->next;

       free(p);
       return 1;

}

// 求表长度
int ListLength(LinkList head)
{
       LinkList p;
       int counter=0;
       p = head;
       while(p!=NULL)
       {
              p=p->next;
              counter++;
       }

       return counter;
}

// 销毁链表
void destoryList(LinkList head)
{
       LinkList p,q;
       p=head;
       while(p!=NULL)
       {
              q=p;
              p=p->next;
              free(q);
       }
}




#endif // LINKLIST_H_INCLUDED

结果

这里面一开始不理解为什么 initList 的时候传的是 A 的地址，而后面的 insertList之类的操作传的就是 A，特地还去问了下：

后面也明白了，一开始 main 里面声明 linkList A的时候，还只是一个指针变量，里面没有存任何东西，后面再 initList 的时候如果不传入 A的地址，那么，由于c语言是 按值 传的，即使在函数里面改变了值，外面的A还是没有改变，这样 A 还是什么都没有存。如果传递了 A的地址，函数里面通过 malloc函数分配内存空间给 head，由于传递的是 A的地址，A这时候就存了一个地址了。而后面的插入操作，直接把A传给函数，就是把 A 结构体首地址传给函数的形参，然后形参是一个指针，他通过链表的首地址来找到结构体，进行插入操作后面，改变了A这个地址所指向的结构体的后续节点，形成链表。
后面的 ListLength 函数传入的是 A，也就是链表的首地址，这样，函数的形参也是地址，它就能通过首地址找到后面的一系列几点，获取长度。
所以后面 A 的值一直都是 首地址，没有改变

参考：