看到太多人在操作链表的时候不知所措,借花献佛,把这段代码弄过来。 链表操作已经全在里面了。至于怎么用,那不关偶事了 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; } }
|