网站 › 『 编程之美 』 › 学习Nisy的C教程第31课--链表双链

lucky_789 发表于 2015-2-8 11:17:36

学习Nisy的C教程第31课--链表双链

本帖最后由 lucky_789 于 2015-2-8 12:03 编辑

第30课视频教程两个半小时，看了几次才看完{:soso_e110:}，模仿着写了个简单的链表和双链。欢迎大家提出宝贵意见。
一、单向链表

/* list1.h -- 单向链表头文件   */

#define NULL 0

typedef int ElementType;

typedef struct _ChainNode
{
      ElementType data;
      struct _ChainNode *next;
}ChainNode;

typedef struct
{
      ChainNode *head;
      ChainNode *tail;
      int total;
}List;

List * ListInit();

/* 销毁链表 */
int ListDestory(List *lp);

/* 向链首插入节点 */
int InsertHead(List *lp, ElementType *pdata);

/* 向链尾插入节点 */
int InsertTail(List *lp, ElementType *pdata);

/* 向链中间插入节点 */
int InsertNode(List *lp, int n, ElementType *pdata);

/* 清空链表 */
int ListClear(List *lp);

/*删除节点 */
int RemoveNode(List *lp, int n);

/* 新建节点 */
ChainNode * NewChainNode(ElementType *pdata);

/* 查找节点 */
ChainNode * GetChainNode(List *lp, int n);

int IsEmpty(List *lp);

/* 遍历显示链表 */
int ListTraverse(List * lp, void (*f)(ElementType *pdata));

/* list1.c -- 单向链表    */

#include "list1.h"

List * ListInit()
{
      List *lp = NULL;
      lp = (List *)malloc(sizeof(List));
      lp->head = NULL;
      lp->tail = NULL;
      lp->total = 0;
      return lp;
}

int ListDestory(List *lp)
{
      ChainNode *p = NULL;
      ChainNode *tmp = NULL;
      if(!lp)
                return 0;
      p = lp->head;
      while(p)
      {
                tmp = p->next;
                free(p);
                p = tmp;
      }
      free(lp);      
      return 1;
}

int ListClear(List *lp)
{
      ChainNode *p = NULL;
      ChainNode *tmp = NULL;
      if(!lp) return 0;

      p = lp->head;
      while(p)
      {
                tmp = p->next;
                free(p);
                p = tmp;
      }
      lp->head = NULL;      
      lp->tail = NULL;
      lp->total = 0;
      return 1;
}

int InsertHead(List *lp, ElementType *pdata)
{
      ChainNode *newp = NULL;

      if(!lp) return 0;

      newp = NewChainNode(pdata);
      if(!newp) return 0;

      if(IsEmpty(lp))
      {
                /* 为空则以此为首节点和尾节点 */
                lp->head = lp->tail = newp;
                lp->total++;
      }
      else
      {
                /* 非空则以新节点为首节点 */
                newp->next = lp->head;
                lp->head = newp;
                lp->total++;
      }
      return 1;
}

int InsertTail(List *lp, ElementType *pdata)
{
      ChainNode *newp = NULL;

      if(!lp) return 0;

      newp = NewChainNode(pdata);
      if(!newp) return 0;

      if(IsEmpty(lp))
      {
                /* 为空则以此为首节点和尾节点 */
                lp->head = lp->tail = newp;
                lp->total++;
      }
      else
      {
                /* 非空则以新节点为尾节点 */
                (lp->tail)->next = newp;
                lp->tail = newp;
                lp->total++;
      }
      return 1;
}

int InsertNode(List *lp, int n, ElementType *pdata)
{
      ChainNode *p = NULL;
      ChainNode *newp = NULL;

      if(!lp) return 0;
      if(n <= 1 || n > lp->total) return 0;

      p = GetChainNode(lp, n - 1);
      if(!p) return 0;

      newp = NewChainNode(pdata);
      if(!newp) return 0;

      newp->next = p->next;
      p->next = newp;
      lp->total++;
      return 1;
}

int RemoveNode(List *lp, int n)
{
      ChainNode *p = NULL;
      ChainNode *tmp = NULL;

      if(!lp) return 0;
      if(n < 1 || n > lp->total) return 0;

      if(lp->total == 1)
      {
                free(lp->head);
                lp->head = NULL;
                lp->tail = NULL;
                lp->total = 0;
      }
      else
      {
                if(n == 1)
                {
                        tmp = (lp->head)->next;
                        free(lp->head);
                        lp->head = tmp;
                        lp->total--;
                }
                else if(n == lp->total)
                {
                        p = GetChainNode(lp, n - 1);
                        p->next = NULL;
                        free(lp->tail);
                        lp->tail = p;
                        lp->total--;
                }
                else
                {
                        p = GetChainNode(lp, n - 1);
                        tmp = (p->next)->next;
                        free(p->next);
                        p->next = tmp;
                        lp->total--;
                }
      }
      return 1;
}

ChainNode * NewChainNode(ElementType *pdata)
{
      ChainNode *p = NULL;
      p = (ChainNode *)malloc(sizeof(ChainNode));
      if(!p) return p;
      memcpy(&p->data, pdata, sizeof(ElementType));
      p->next = NULL;
      return p;
}

int IsEmpty(List *lp)
{
      return lp->total == 0;
}

ChainNode * GetChainNode(List *lp, int n)
{
      ChainNode *p = NULL;
      int i = 0;

      if(!lp) return 0;
      if(n < 1 || n > lp->total) return 0;

      for(i = 1, p = lp->head; i < n; i++, p = p->next);

      return p;
}

int ListTraverse(List * lp, void (*pfn)(ElementType *pdata))
{
      int i = 0;
      ChainNode *p = NULL;
      if(!lp) return 0;
      /* for (p = lp->head; p; p = p->next) */
      for (p = lp->head, i = 0; i < lp->total; i++, p = p->next)
                pfn(&p->data);
      printf("\n");
      return 1;
}

/* test1.c -- 单向链表   */
/* 和list1.c一起编译       */


#include "List1.h"

void myprintf(ElementType * pdata)
{
      printf("%d ", *pdata);
}

int main()
{
      int i;
      List *lp = ListInit();
      ElementType a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
      ElementType data = 99;

      if(!lp)
      {
                printf("\nInitList error!\n");
                return 0;
      }

      for (i = 0; i < 10; i++)
      {
                InsertTail(lp, a+i);
      }

      ListTraverse(lp, myprintf);

      InsertHead(lp, &data);
      ListTraverse(lp, myprintf);

      InsertTail(lp, &data);
      ListTraverse(lp, myprintf);

      InsertNode(lp, 3, &data);
      ListTraverse(lp, myprintf);

      RemoveNode(lp, 3);
      ListTraverse(lp, myprintf);

      RemoveNode(lp, 12);
      ListTraverse(lp, myprintf);

      RemoveNode(lp, 1);
      ListTraverse(lp, myprintf);

      ListDestory(lp);
      return 1;
}

二、双向链表（在单向链表的基础上略加修改而来）

/* list2.h -- 双向链表头文件   */

#define NULL 0

typedef int ElementType;

typedef struct _ChainNode
{
      struct _ChainNode *prev;
      ElementType data;
      struct _ChainNode *next;
}ChainNode;

typedef struct
{
      ChainNode *head;
      ChainNode *tail;
      int total;/* 保留此项主要是考虑以空间换时间。其实程序体还节省了更多的代码空间 */
}List;

List * ListInit();

int ListDestory(List *lp);

int InsertHead(List *lp, ElementType *pdata);

int InsertTail(List *lp, ElementType *pdata);

int InsertNode(List *lp, int n, ElementType *pdata);

int ListClear(List *lp);

int RemoveNode(List *lp, int n);

ChainNode * NewChainNode(ElementType *pdata);

ChainNode * GetChainNode(List *lp, int n);

int IsEmpty(List *lp);

int ListTraverse(List * lp, void (*f)(ElementType *pdata));

/* list2.c -- 双向链表      */

#include "list2.h"

List * ListInit()
{
      List *lp = NULL;
      lp = (List *)malloc(sizeof(List));
      lp->head = NULL;
      lp->tail = NULL;
      lp->total = 0;
      return lp;
}

int ListDestory(List *lp)
{
      ChainNode *p = NULL;
      ChainNode *tmp = NULL;
      if(!lp) return 0;

      p = lp->head;
      while(p)
      {
                tmp = p->next;
                free(p);
                p = tmp;
      }
      free(lp);      
      return 1;
}

int ListClear(List *lp)
{
      ChainNode *p = NULL;
      ChainNode *tmp = NULL;
      if(!lp) return 0;

      p = lp->head;
      while(p)
      {
                tmp = p->next;
                free(p);
                p = tmp;
      }

      lp->head = NULL;      
      lp->tail = NULL;
      lp->total = 0;
      return 1;
}

int InsertHead(List *lp, ElementType *pdata)
{
      ChainNode *newp = NULL;

      if(!lp) return 0;

      newp = NewChainNode(pdata);
      if(!newp) return 0;

      if(IsEmpty(lp))
      {
                /* 为空则以此为首节点和尾节点 */
                lp->head = lp->tail = newp;
                lp->total++;
      }
      else
      {
                /* 非空则以新节点为首节点 */
                (lp->head)->prev = newp;
                newp->next = lp->head;
                lp->head = newp;
                lp->total++;
      }
      return 1;
}

int InsertTail(List *lp, ElementType *pdata)
{
      ChainNode *newp = NULL;

      if(!lp) return 0;

      newp = NewChainNode(pdata);
      if(!newp) return 0;

      if(IsEmpty(lp))
      {
                /* 为空则以此为首节点和尾节点 */
                lp->head = lp->tail = newp;
                lp->total++;
      }
      else
      {
                /* 非空则将新节点接在后面 */
                (lp->tail)->next = newp;
                newp->prev = lp->tail;
                lp->tail = newp;
                lp->total++;
      }
      return 1;
}

int InsertNode(List *lp, int n, ElementType *pdata)
{
      ChainNode *p = NULL;
      ChainNode *newp = NULL;

      if(!lp) return 0;
      if(n <= 1 || n > lp->total) return 0;

      p = GetChainNode(lp, n - 1);
      if(!p) return 0;

      newp = NewChainNode(pdata);
      if(!newp) return 0;

      /* 插入点后的节点的prev指向新节点 */
      (p->next)->prev = newp;

      /* 新节点的next指向插入点后的节点 */
      newp->next = p->next;

      /* 新节点的prev指向插入点前的节点 */
      newp->prev = p;

      /* 插入点前的节点的next指向新节点 */
      p->next = newp;

      lp->total++;
      return 1;
}

int RemoveNode(List *lp, int n)
{
      ChainNode *p = NULL;

      if(!lp) return 0;
      if(n < 1 || n > lp->total) return 0;

      if(lp->total == 1)
      {
                /* 只有一个节点则清除之 */
                free(lp->head);
                lp->head = NULL;
                lp->tail = NULL;
                lp->total = 0;
      }
      else
      {
                if(n == 1)
                {
                        /* 删除多节点的首节点，先保存第二节点 */
                        p = (lp->head)->next;

                        /* 删除首节点 */
                        free(lp->head);

                        /* 将第二节点设为首节点 */
                        p->prev = NULL;
                        lp->head = p;

                        lp->total--;
                }
                else if(n == lp->total)
                {
                        /* 删除多节点的尾节点，先保存倒数第二节点 */
                        p = (lp->tail)->prev;

                        /* 删除尾节点 */
                        free(lp->tail);

                        /* 将倒数第二节点设为尾节点 */
                        p->next = NULL;
                        lp->tail = p;

                        lp->total--;
                }
                else
                {
                        /* 删除多节点的中间节点，获取删除节点信息 */
                        p = GetChainNode(lp, n);

                        /* 删除点前一节点的next设为删除点后一节点 */
                        (p->prev)->next = p->next;

                        /* 删除点后一节点的prev设为删除点前一节点 */
                        (p->next)->prev = p->prev;

                        /* 删除节点 */
                        free(p);

                        lp->total--;
                }
      }
      return 1;
}

ChainNode * NewChainNode(ElementType *pdata)
{
      ChainNode *p = NULL;
      p = (ChainNode *)malloc(sizeof(ChainNode));
      if(!p) return p;
      memcpy(&p->data, pdata, sizeof(ElementType));
      p->prev = NULL;
      p->next = NULL;
      return p;
}

int IsEmpty(List *lp)
{
      return lp->total == 0;
}

ChainNode * GetChainNode(List *lp, int n)
{
      ChainNode *p = NULL;
      int i = 0;

      if(!lp) return 0;
      if(n < 1 || n > lp->total) return 0;

      for(i = 1, p = lp->head; i < n; i++, p = p->next);

      return p;
}

int ListTraverse(List * lp, void (*pfn)(ElementType *pdata))
{
      ChainNode *p = NULL;
      if(!lp) return 0;

      for (p = lp->head; p; p = p->next)
                pfn(&p->data);
      printf("\n");
      return 1;
}

/* test2.c -- 单向链表      */
/* 和list2.c一起编译      */


#include "List2.h"

void myprintf(ElementType * pdata)
{
      printf("%d ", *pdata);
}

int main()
{
      int i;
      List *lp = ListInit();
      ElementType a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
      ElementType data = 99;

      if(!lp)
      {
                printf("\nInitList error!\n");
                return 0;
      }

      for (i = 0; i < 10; i++)
      {
                InsertTail(lp, a+i);
      }

      ListTraverse(lp, myprintf);

      InsertHead(lp, &data);
      ListTraverse(lp, myprintf);

      InsertTail(lp, &data);
      ListTraverse(lp, myprintf);

      InsertNode(lp, 3, &data);
      ListTraverse(lp, myprintf);

      RemoveNode(lp, 3);
      ListTraverse(lp, myprintf);

      RemoveNode(lp, 12);
      ListTraverse(lp, myprintf);

      RemoveNode(lp, 1);
      ListTraverse(lp, myprintf);

      ListDestory(lp);
      return 1;
}

Nisy 发表于 2015-2-9 10:56:18

赞！学编程非写代码，拍错误方可学会。Why，因为语法不是我们定义的，编译器不是我们实现的，所以必须要动手写代码才能学会编程。

还有一种实现在这里：http://www.sicaril.com/thread-529-1-2.html

查看完整版本: 学习Nisy的C教程第31课--链表双链