#include<stdio.h> #define false 0 #define ok 1 //定义节点的结构 typedef struct node{ int data; struct node *next; }node; typedef struct node *linklist; //初始化链表,创建一个链表并赋值 void creatlist(linklist *l,int n) { linklist p; (*l) = (linklist)malloc(sizeof(node)); (*l)->next = NULL; int i; for (i = 0; i < n; i++) { p= (linklist)malloc(sizeof(node)); p->data = i; p->next = (*l)->next; (*l)->next = p; } } //链表查询 int getelem(linklist l, int i, int *e) { int k = 1; linklist p=NULL; p = l->next; while (p&&k<i) { p = p->next; k++; } if (!p || k>i) return false; *e = p->data; return ok; } //链表特定位置插入元素 int listinsert(linklist *l, int i, int e) { int k = 1; linklist s=NULL, p=NULL; p = *l; int j = 1; while (p&&j<i) { p = p->next; j++; } if (!p || k>i) return false; s = (linklist)malloc(sizeof(node)); s->data = e; s->next = p->next; p->next = s; return ok; } //链表特定位置删除元素 int listdelete(linklist *l, int i, int *e) { int j = 1; linklist p=NULL, q=NULL; p = *l; while (p&&j<i) { p = p->next; j++; } if (!p->next || j>i) return false; q = p->next; p->next = q->next; *e = q->data; free(q); return ok; } //打印链表 int seelist(linklist l) { linklist p=NULL; p = l->next; int k = 0; while (p) { printf("%4d", p->data); p = p->next; k++; } if (k == 0) { printf("链表为空"); return false; } return ok; } //删除整个链表 int clearlist(linklist *l) { linklist p = NULL,q=NULL; p = (*l)->next; while (p) { q = p->next; free(p); p = q; } (*l)->next = NULL; return ok; } int main(void) { int a; linklist lb; creatlist(&lb, 5); seelist(lb); listinsert(&lb, 2, 0); seelist(lb); listdelete(&lb, 2, &a); seelist(lb); clearlist(&lb); return 0; }
1、刚申请指针就要指向NULL;给指针初始化时,如果不是规定它指向某个地址就要malloc申请空间;不用的指针要free。
2、typedef struct node linklist;这语句的含义是以后linklist就代表struct node 。这里的好处是编程更美观简洁。毕竟要用到指向指针的指针,不用这个typedef等下就要出现**。
3、以上代码头指针指向了头结点,这个链表拥有头结点,但是其实这种指向头结点的头指针可以不需要指向指针的指针
下面说明为什么可以不要使用指向指针的指针
头指针是链表必须的元素,linklist p,这里定义了头指针,头指针通常代表该链表的名字,如果头指针p就是头结点,含有data、next,直接对调用p做参数,就可以更改p指向的结构的值,不需要指向指针的指针
先看一段简单代码:
#include<stdio.h> #include<stdlib.h> typedef struct node { int data; struct node *next; }node,*link; //初始化头结点,此时头指针就是头结点 void init(link p) { p->data = 0; p->next = NULL; } //插入元素 void insrt(link p, int i,int a) { int j = 1; link b= (link)malloc(sizeof(node)); link c = p; while (j < i) { c = c->next; j++; } b->data = a; b->next = c->next; c->next = b; } //显示链表 void seeq(link q) { link b = q->next; while (b != NULL) { printf("%d", b->data); b = b->next; } } void main() { int i; link l1 = (link)malloc(sizeof(node)); init(l1); for (i= 1; i < 5; i++) { insrt(l1, i, i); } seeq(l1); }
对段长的代码进行改变也无需指向指针的指针,我们把所有的*l改成l,再把主函数里的&去掉
#include<stdio.h> #define false 0 #define ok 1 typedef struct node { int data; struct node *next; }node,*linklist; void creatlist(linklist l, int n) { linklist p; //去掉了l = (linklist)malloc(sizeof(node)); l->next = NULL; int i; for (i = 0; i < n; i++) { p = (linklist)malloc(sizeof(node)); p->data = i; p->next = l->next; l->next = p; } } int getelem(linklist l, int i, int *e) { int k = 1; linklist p = NULL; p = l->next; while (p&&k<i) { p = p->next; k++; } if (!p || k>i) return false; *e = p->data; return ok; } int listinsert(linklist l, int i, int e) { int k = 1; linklist s = NULL, p = NULL; p = l; int j = 1; while (p&&j<i) { p = p->next; j++; } if (!p || k>i) return false; s = (linklist)malloc(sizeof(node)); s->data = e; s->next = p->next; p->next = s; return ok; } int listdelete(linklist l, int i, int *e) { int j = 1; linklist p = NULL, q = NULL; p = l; while (p&&j<i) { p = p->next; j++; } if (!p->next || j>i) return false; q = p->next; p->next = q->next; *e = q->data; free(q); return ok; } int seelist(linklist l) { linklist p = NULL; p = l->next; int k = 0; while (p) { printf("%4d", p->data); p = p->next; k++; } if (k == 0) { printf("链表为空"); return false; } return ok; } int clearlist(linklist l) { linklist p = NULL, q = NULL; p = l->next; while (p) { q = p->next; free(p); p = q; } l->next = NULL; return ok; } int main(void) { int a; linklist lb = (linklist)malloc(sizeof(node));//这里有变动! creatlist(lb, 5); seelist(lb); listinsert(lb, 2, 0); seelist(lb); listdelete(lb, 2, &a); seelist(lb); clearlist(lb); return 0; }
可以看到除了&和,还有两处变动,就是把原本init函数内的为指针申请空间改到了主函数内一开始申明头指针时就申请空间,否则会报错:使用了未初始化的局部变量lb。这是因为,刚申明指针时,即linklist lb,编译器会为lb分配空间(32位系统4字节,64位系统8字节),此时lb的地址是已知的,但是lb的值时不知道的(malloc时才会定下来lb的值)。如果函数调用不知道值的lb,是没办法调用的。而如果函数是调用lb的地址,因为lb的地址是已知的,就可以调用了,可以在函数内再为lb申请空间。即函数调用的参数一定是初始化值了的参数*
但是实际上,如果头指针linklist p,p的值就是一个单纯的指针,它的值就是个结点的地址。按照上面的方法,我们想在链表头插入一个结点b,b的地址为xxx,p->next=地址xxx,此时就改变了个结点的next的值,即个结点指向地址xxx,即b变成了第二个结点,没办法做到让b变成个结点!所以需要改变p的值,让p指向b,既然改变指针本身的值,而不是指针指向的对象的值,就需要用到指向指针的指针了。
想要了解更多的c++应用技术那就加入我们吧!