论坛: 编程破解 标题: 一个链表的源代码[zt] 复制本贴地址    
作者: TomyChen [quest]    版主   登录
看到太多人在操作链表的时候不知所措,借花献佛,把这段代码弄过来。
链表操作已经全在里面了。至于怎么用,那不关偶事了
VC6下通过编译


代码:

#include <stdio.h>
#include <malloc.h>
#include <string.h>
#include <conio.h>



/* 书中的常量定义 */
#define OK    1
#define ERROR  0
#define OVERFLOW (-1)



typedef int Status;
/* 定义了一个学生的结构体 */
typedef struct {
   int sn;    /* 学号 */
   char name[32]; /* 姓名 */
   int score;   /* 成绩 */
} data_t;
/* 定义了链表的节点形式为一个单链表 */
typedef struct LNODE {
   data_t data;
   struct LNODE * next;
}node_t, *link_t;
/* 创建一个有头节点的链表*/
link_t create_link();
/* 销毁链表,释放节点空间 */
void  destroy_link(link_t head);
/* 在链表的第 idx 位置插入一个节点,节点的值由 d 给出*/
/* 注意 idx 为插入节点后的位置,且从0开始计算 */
Status insert_node(link_t head, int idx, data_t e);
/* 删除链表的第 idx 个节点,并将删除的内容填入e所指向的空间*/
/* idx也是从0开始计算 */
Status delete_node(link_t head, int idx, data_t* e);
/* 判断链表是否为空 */
Status empty_link(link_t head);
/* 获得链表的长度 */
int length_link(link_t head);
/* 获得链表的第i个元素的位置,并返回执行该元素的指针,NULL表示无效 */
node_t* locate_link(link_t head, int idx);
/* 打印链表的内容 */
void print_link(link_t head);
/* 将一个链表倒置 */
void reverse_link(link_t head);
/* 键盘命令映射表 */
const char *help[] =
{
 "?,h,H  -- this help\n",
 "a,A,i,I -- add a node, ex: a 10\n",
 "d,D   -- del a node, ex: d 10\n",
 "p,P   -- print this link\n",
 "g,G   -- get link num\n",
 "r,R   -- reverse the link\n",
 "x,X,q,Q -- exit this program\n",
};


/* 程序入口 */
int main(int argc, char* argv[])
{
 char cmd;
 int i, idx;
 data_t tmp;
 link_t head = create_link();
 for (i=0; i<10; i++)  
 { /*预先插入10个节点*/
  tmp.sn = i; tmp.score = 100-i; strcpy(tmp.name, "ttttt");
  insert_node(head, i, tmp);
 }
 print_link(head);
 printf("input command: ");
 while ( cmd = getch())
 {
  printf("%c\n", cmd);
  switch (cmd)
   {
    case '?': case 'h':   case 'H': /*打印帮助信息*/
    for (i=0; i<sizeof(help)/sizeof(help[0]); i++)
      printf("\t%s", help[i]);
    printf("\n");
    break;
    case 'a': case 'A':   case 'i': case 'I': /*插入一个节点*/
    printf("please input where do you want to insert: ");
    scanf("%d", &idx);
    if (idx < 0 || idx > length_link(head)) 
    {
     printf("insert pos error!\n");
     break;
    }
    printf("please input the SN, name and score:");
    scanf("%d%s%d", &tmp.sn, tmp.name, &tmp.score);
    if (insert_node(head, idx, tmp) == ERROR)
    {
     printf("insert error!\n");
     break;
    }
    printf("insert OK!\n");
    print_link(head);
    break;
    case 'd': case 'D': /*删除一个节点*/
    printf("please input which do you want to delete: ");
    scanf("%d", &idx);
    if (idx < 0 || idx >= length_link(head)) 
    {
     printf("delete pos error!\n");
     break;
    }
    if (delete_node(head, idx, &tmp) == NULL)
    {
     printf("input error!\n");
     break;
    }
    printf("delete OK\n");
    print_link(head);
    break;
    case 'p': case 'P': /* 打印链表*/
    print_link(head);
    break;
    case 'x': case 'X':   case 'q':   case 'Q':/*退出程序*/
    destroy_link(head);
    return 0;
    case 'r': case 'R': /*倒置链表*/
    reverse_link(head);
    printf("this link have been reversed!\n");
    print_link(head);
    break;
    default:
    printf("input error!, for help, please input ?\n");
   }
   printf("\n\ninput command: ");
 }
 return 0;
}


link_t create_link()
{
 link_t head;
 head = (link_t)malloc(sizeof(node_t));
 head->next = NULL;
 head->data.sn = 0;
 return head;
}
void  destroy_link(link_t head)
{
 node_t *p = head;
 while (head != NULL)
 {
  p = head->next;
  free (head);
  head = p;
 }
}
void  print_link(link_t head)
{
 node_t *p = head->next; /*跳过头节点*/
 int cnt = 0;
 printf("pos : SN %20s score\n", "name   ");
 while (p != NULL)
 {
  printf("%04d: %4d%20s%4d\n",cnt++, p->data.sn, p->data.name, p->data.score);
  p = p->next;
 }
}

Status  empty_link(link_t head)
{
 if (head==NULL || head->next == NULL)
  return OK;
 else
  return ERROR;
}

int  length_link(link_t head)
{
 int len = 0;
 node_t *p = head->next;
 for(; p!=NULL; p = p->next)
  len++;
 return len;
}



node_t* locate_link(link_t head, int idx)
{
 int pos = -1;
 node_t *p = head;
 while (p!=NULL && pos < idx)
 {
  p = p->next; pos ++;
 }
 return p;
}
Status insert_node(link_t head, int idx, data_t e)
{
  node_t *add = NULL; /* 待加入的节点指针 */
  node_t *p = locate_link(head, idx-1); /*注意查询idx-1*/
  if (p == NULL) return ERROR;
  add = (node_t *)malloc(sizeof(node_t));
  add->data = e;
  add->next = p->next;
  p->next = add;
  return OK;
}

Status delete_node(link_t head, int idx, data_t *e)
{
  node_t *p = locate_link(head, idx-1); /*注意查询idx-1*/
  node_t *q = NULL; /* p为待删除的节点指针 */
  if (p == NULL || p->next== NULL) return ERROR;
  q = p->next;
  *e = q->data;
  p->next = q->next;
  free (q);
  return OK;
}



void reverse_link(link_t head)
{
  node_t *p1, *p2;
  p1 = head->next;
  head->next = NULL;
  while (p1 != NULL)  
  {
   p2 = p1->next;
   p1->next = head->next;
   head->next = p1;
   p1 = p2;
  }
}



地主 发表时间: 04-02-19 09:29

回复: sniper167 [sniper167]   论坛用户   登录


B1层 发表时间: 04-02-19 13:10

论坛: 编程破解

20CN网络安全小组版权所有
Copyright © 2000-2010 20CN Security Group. All Rights Reserved.
论坛程序编写:NetDemon

粤ICP备05087286号