链表是一种常见的基础数据结构,它由一系列节点(Node)组成。每个节点包含两部分:数据域(存储数据)和指针域(存储下一个节点的地址)。链表的特点是元素在内存中不一定连续存储,而是通过指针连接起来。
以下是链表的一些基本特点:
- 动态性:链表的长度可以动态变化,不需要在创建时指定大小。
- 灵活性:链表可以方便地插入和删除元素,不需要像数组那样进行大量元素的移动。
- 多样性:链表有多种形式,如单向链表、双向链表、循环链表等。
以下是链表的主要类型:
- 单向链表:每个节点只有一个指针,指向下一个节点。
- 双向链表:每个节点有两个指针,一个指向前一个节点,另一个指向下一个节点。
- 循环链表:链表中最后一个节点的指针指向第一个节点,形成一个环。
1. 链表操作简介
在操作链表之前,要先来设计链表中每个结点的数据结构。我们设计一个学生的结构体变量,用来存放学生的学号和分数。
struct ST{int n;int score;struct ST *next;
};
在 C 语言中,指针必须指定它所指向的数据类型。由于
next
需要指向链表中的下一个struct ST
类型的节点,因此它的类型必须是struct ST *
。另外,为了处理方便,通常都是在线性单向链表的第一个结点之前额外增加一个结点,称之为“头结点”。
2. 空链表的建立
这里所说的空链表,是指只含有一个头结点的链表。
struct ST *createNullList()
{struct ST* head;head=(struct ST*)malloc(sizeof(struct ST));if(head!=NULL)head->next=NULL;elseprintf("Out of space!\n");return head;
}
动态内存分配有可能失败,因此需要检查head中 所存的值是否为NULL。若为NULL,表示空间分配失败,若不为NULL,则表示头结点已经成功分配。由于空链表没有实际结点,因此头结点的指针域应该存为NULL。
3. 判断链表是否为空
int isNullList(struct ST* head) //传进去头指针
{return head->next==Null; //判断语句
}
4. 在链表最后添加一个结点
int append(struct ST* head, int n, int s)
{struct ST* p,*pnew;pnew = (struct ST*)malloc(sizeof(struct ST));if(pnew==NULL){printf("Out of space!");return 0;}else{pnew->n=n;pnew->sorce=s;p=head; //p先指向头结点while(p->next!=NULL) //若p所指不是链尾p=p->next; //p后移一个结点p->next=pnew; //链尾的next存储新结点指针pnew->next=NULL; //使新结点成为链尾}return 1;
}
5. 求某结点的指针
例如,要查找链表中学号为n的结点的指针。
查找要从链表的第一个结点开始,依次将每个结点的学号与n比较,若找到该同学,返回其地址,若找不到,则返回NULL。
struct ST* locate(struct ST* head, int n)
{struct ST* p;p=head->next; //将头结点的next域赋值给P,使指向第一个结点while(p!=NULL&&p->n!=n) //如果p存的不是NULL(表示P指向一个实际存在的结点)p=p->next;return p;
}
6. 求p所指结点的前驱(前一个结点)
struct ST* locatePre(struct ST* head, struct ST* p)
{struct ST* ptemp;ptem=head;while(ptemp!=NULL&&ptemp->next!=p)ptemp=ptemp->next;return ptemp;
}
判断ptemp是不是等于NULL以及ptemp->next是不是等于p;
若两者都不是,则执行ptemp=ptemp->next,重复上一个步骤;
若ptemp等于NULL,表示已经找遍所有结点但没有找到p所指的结点,退出循环,返回NULL。若ptemp->next=p,则ptemp所指结点就是p所指结点的前驱,退出循环,返回ptemp。
7. 在某结点之后插入一个新结点
int insert(struct ST* head, struct ST* p, int n, float score)
{struct ST* pnew=(struct ST*)malloc(sizeof(struct ST));if(pnew==NULL){printf("Out of space!\n");return 0;}pnew->num=n;pnew->score=score;pnew->next=p->next;p->next=pnew;return 1;
}
8. 结点的删除
int delete(struct ST* head, int n)
{struct ST *p1,*p2;p1=head;//下面用循环来查找学号为n的结点的前驱while(p1->next!=NULL&&p1->next!=n)p1=p1->next;if(p1->next==NULL){printf("Not exist!\n");return 0;}p2=p1->next;p1->next=p2->next;free(p2);return 1;
}