---

發信人: tucson.bbs@bbs.ee.nsysu.edu.tw (愛睡了), 看板: C_and_CPP
標  題: Re: 教一下
發信站: 漢神小站 (Fri Apr 16 02:32:31 1999)
轉信站: Ptt!CSZoneNews!Handxon

※ 引述《imlex.bbs@ptt.csie.ntu.edu.tw (不知名最珍貴)》之銘言：
: 可不可以交我一下簡單的三個程式
: 一為鏈結串列
: 二為增加一個點
: 且在前、中、後加入
: 三為刪除一個點
: 也是前中後


下面這個可以了吧....
如果還不行的話要再去找書了....

#include <stdlib.h>

struct clist                      /* 環狀串列結構宣告     */
{
   int data;                      /* 節點資料             */
   struct clist *next;            /* 指向下一節點的指標   */
};
typedef struct clist cnode;       /* 環狀串列新型態       */
typedef cnode *clink;             /* 環狀串列指標新型態   */

/* ---------------------------------------- */
/*  環狀鍵結串列的列印                      */
/* ---------------------------------------- */
void print_clist(clink head)
{
   clink ptr;

   head = head->next;             /* 指向串列第一個節點   */
   ptr = head;                    /* 指向串列開始         */
   do                             /* 串列走訪迴路         */
   {
      printf("[%d]",ptr->data);   /* 列印節點資料         */
      ptr = ptr->next;            /* 指向下一個節點       */
   } while ( head != ptr && head != head->next );
   printf("\n");                  /* 換行                 */
}

/* ---------------------------------------- */
/*  環狀鍵結串列的節點插入                  */
/* ---------------------------------------- */
clink insert_node(clink head,clink ptr,int value)
{
   clink new_node;                /* 新節點的指標         */

   /* 建立新節點配置節點記憶體 */
   new_node = ( clink ) malloc(sizeof(cnode));
   if ( !new_node )               /* 檢查記憶體指標       */
      return NULL;
   new_node->data = value;        /* 建立節點內容         */
   new_node->next = NULL;         /* 設定指標初值         */

   if ( head == NULL )            /* 如果串列是空的       */
   {
      new_node->next = new_node;  /* 指向自身節點         */
      return new_node;            /* 傳回新節點指標       */
   }

   if ( ptr == NULL )
   {
      /* 第一種情況: 插在第一節點之前 */
      new_node->next = head->next;  /* 新節點指向第一節點 */
      head->next->next = new_node;  /* 前一節點指向新節點 */
   }
   else
   {
      /* 第二種情況: 插在節點之後 */
      new_node->next = ptr->next; /* 新節點指向下一節點   */
      ptr->next = new_node;       /* 前一節點指向新節點   */
   }
   if ( ptr == head )             /* 插入最後一個節點     */
      head = new_node;            /* 改變串列開始         */

   return head;                   /* 傳回串列起始指標     */
}

/* ---------------------------------------- */
/*  環狀鍵結串列的節點刪除                  */
/* ---------------------------------------- */
clink delete_node(clink head,clink ptr)
{
   clink previous;                /* 前一節點指標         */

   if ( head == NULL )            /* 如果串列是空的       */
      return NULL;


   if ( ptr == head->next )       /* 如果是第一節點       */
   {
      /* 第一種情況: 刪除第一個節點 */
      head->next = ptr->next;     /* 前節點指向下節點     */
   }
   else
   {
      /* 第二種情況: 刪除中間節點 */
      previous = head;
      if ( head != head->next )   /* 串列多於一個節點     */
         while ( previous->next != ptr ) /*找節點ptr的前節點*/
            previous = previous->next;   /* 移至下一個節點  */
      previous->next = ptr->next; /* 前節點指向下節點     */
   }
   if ( ptr == head )             /* 刪除最後一個節點     */
      head = previous;            /* 改變串列開始         */
   free(ptr);                     /* 釋回節點記憶體       */

   return head;                   /* 傳回串列起始指標     */
}

/* ---------------------------------------- */
/*  主程式:                                 */
/*  使用插入節點的方式來建立串列, 完成後將  */
/*  串列內容印出. 而後刪除前後兩節點.       */
/* ---------------------------------------- */
void main()
{
   clink head = NULL;             /* 環狀鍵結串列指標     */
   int list[6] = { 9, 7, 3, 4, 5, 6 };   /* 陣列內容      */
   int i;

   head = insert_node(head,head,list[0]); /*建立第一個節點 */
   printf("建立第一節點:     ");
   print_clist(head);             /* 印出串列             */
   /* 第一種情況: 插在第一節點前 */
   head = insert_node(head,NULL,list[1]);
   printf("插入第一節點之前: ");
   print_clist(head);             /* 印出串列             */
   for ( i = 2; i < 6; i++ )      /* 建立串列節點         */
   {
      /* 第二種情況: 插在節點之後 */
      head = insert_node(head,head->next,list[i]);
      printf("插入節點之後:     ");
      print_clist(head);          /* 印出串列             */
   }
   /* 第一種情況: 刪除第一個節點 */
   head = delete_node(head,head->next);
   printf("刪除第一個節點:   ");
   print_clist(head);             /* 印出串列             */
   /* 刪除最後一個節點 */
   printf("刪除最後一個節點: ");
   head = delete_node(head,head);
   print_clist(head);             /* 印出串列             */
}
--
   ※發信站: 漢神小站 <bbs.ee.nsysu.edu.tw>
    ◆ From: 140.117.184.35


--
Shaken, Not Stirred.
--
※ 作者: TL 時間: 2013-01-27 18:27:28