定义一个单链表类
typedef struct node
{ int data;
struct node *next;
}linklist;
(1)逐个输出单链表中所有数据元素。
void Printlist(linklist *q)
{
while(q)
{
printf("%d ",q->data);
q=q->next;
}
}
(2)单链表定位操作。其定位功能为:在单链表中查找是否存在数据元素x,如果存在,返回单链表中和x值相等的第1个数据元素的序号(序号从0开始编号);如果不存在,返回-1。
int ListLocate_L(linkList L, ElemType x)
{
linkList p=L;
int i=0;
while(p->next!=0)
{
if(p->next->data==x){
return i;
} else{
p=p->next;
i++;
}
return -1;
]
(3)删除单链表中所有值为x的元素。
void delete_X(linkList L,int x){
linkList p = L->next, pre = L, q; //p指针从第一个元素结点开始,pre指针从头结点开始
while(p != NULL){
if(p->val == x){
q = p; //复制给辅助指针q用来释放空间
p = p->next; //p往后遍历
pre->next = p; //将pre->next指向当前p
free(q); //上一个值为X的元素已经从链表中删除,释放结点空间
} else {
p = p->next; // 这里注意 p 和 pre都要后移,因为pre始终是p的前驱
pre = pre->next;
}
}
}
(4)就地逆置单链表中的数据元素。
linklist *InverseLinklist(linklist *q)
{
linklist *p,*head;
p=head->next;
if(p!=NULL) {
p=p->next;
head->next->next=NULL;
}
while(p!=NULL){
q=p->next;
p->next=head->next;
head->next=p;
p=q;
}
}
(5)将单链表中数据元素就地排序。所谓就地排序是指在排序过程中利用原有的结点,不额外增加新结点。
void SortSingleList(listlist *head)
{
listlist *pre=head,*p=pre->next,*q,*r; //pre指向head,p指向第一个元素
q=p->next; //q指向待比较节点
p->next=NULL; //第一个节点next截止 NULL
while(q!=NULL)
{
while(pre->next!=NULL && q->data>pre->next->data)//查找插入点的前驱节点
pre=pre->next;
r=q->next; //保存待比较的下一个节点
q->next=pre->next;
pre->next=q; //插入节点
pre=head; //恢复pre的head
q=r; //q指向下一个待比较节点
}
}
(6)在单链表有序的前提下,插入一个数据元素x,要求插入后的单链表中数据元素从小到大有序排列。
linklist *Insert(linklist *head,int x)
{
linklist *s,*q;
s=(linklist*)malloc(sizeof(linklist));
s->data=x;
q=head;
if(q->data>x){
s->next=q;
head=s;
}else{
while(q!=NULL)
{
if(q->next->data>x){
s->next=q->next;
q->next=s;
break;
}
q=q->next;
}
q=head;
}
}