Question

1.建立带头结点的单链表；

1.建立带头结点的单链表；
2.输出带头结点的单链表；
3.将单链表中第pos个结点和其前驱结点的相应逻辑顺序进行交换；
4.以选择法对单链表进行排序；
5.在主函数实现对上述四个函数的调用，输出运行结果。
大家帮帮忙，给个具体一点的，谢谢了

Answer 1

　　建立方法：
　　带头结点初始化
　　Node *head; //声明头结点

void InitList(Node **head){
*head=(Node *)malloc( sizeof(Node));
(*head)->next=NULL;
}

　　带头结点尾插入，统一操作。
　　方式一：
　　void CreatList(Node **head){
Node *r=*head,*s;
int a;
while(scanf("%d",&a)){
if(a!=0){
s=(Node *)malloc(sizeof(Node));
s->value=a;
r->next=s;
r=s;
}
else{
r->next=NULL;
break;
}
}
}

　　调用CreatList(&head);
　　方式二：
　　void CreatList(Node *head){
Node *r=head,*s;
... //下面的都一样
}

　　调用CreatList(head);
　　不带头结点初始化
　　方式一：
　　void InitList(Node **head){
*head=NULL;
}

　　调用InitList(&head);
　　方式二：
　　void InitList(Node *head){
head=NULL;
}

　　调用InitList(head);
　　不带头结点尾插入，第一个节点与其他节点分开操作。
　　void CreatList(Node **head){
Node *p,*t; /*p工作指针,t临时指针*/
int a,i=1;
while(scanf("%d",&a)){
if(a!=0){
t=(Node *)malloc(sizeof(Node));
t->value=a;
if(i==1){
*head=t;
}
else{
p->next=t;
}
p=t;
}
else{
p->next=NULL;
break;
}
i++;
}
}

　　调用CreatList(&head);
　　两种初始化方法的区别
　　不带头结点的单链表对于第一个节点的操作与其他节点不一样，需要特殊处理，这增加了程序的复杂性和出现bug的机会，因此，通常在单链表的开始结点之前附设一个头结点。
　　带头结点的单链表，初始时一定返回的是指向头结点的地址，所以一定要用二维指针，否则将导致内存访问失败或异常。
　　带头结点与不带头结点初始化、插入、删除、输出操作都不样，在遍历输出链表数据时，带头结点的判断条件是while(head->next!=NULL)，而不带头结点是while(head!=NULL)，虽然头指针可以在初始时设定，但是如1所述，对于特殊情况如只有一个节点会出现问题。

Answer 2

我空间上我做的一个
http://hi.baidu.com/crazy%B3%CC%D0%F2%D4%B1/blog/item/21181a2de38289eb8b139956.html

Answer 3

//我用的是VC6.0，因为不是很熟练，还是得看着书写，类C的语言
#include<stdio.h>
#include<malloc.h>

#define OK 1
#define ERROR 0
#define NULL 0

typedef int Status;
typedef int ElemType;

typedef struct LNode{
ElemType data;
struct LNode *next;
}LNode,*LinkList;

int len; //因为要后面需要调用表长，所以定义为全局变量
//算法有待改进

Status CreatList_L(LinkList &L) {
//逆位序输入n个元素的值，建立带表头结点的单链线性表L
// int len;
printf("\nInput the amount of List:");
scanf("%d",&len);
L=(LinkList)malloc(sizeof(LNode));
L->next=NULL; //先建立一个带头结点的单链表
printf("\nInput the List:");
for(int i=len;i>0;--i){
LinkList p=(LinkList)malloc(sizeof(LNode));
scanf("%d",&p->data); //输入元素值
p->next=L->next; //插入到表头
L->next=p;
}
return OK;
}

Status ListInsert_L(LinkList &L,int i,ElemType e){
//在带头结点的单链表L中第i个位置插入元素e
LinkList p=L;
int j=0;
while(p && j<i-1)
{
p=p->next;
++j;
} //寻找第i-1个结点
if(!p || j>i-1) return ERROR; //i小于1或者大于表长+1
LinkList s=(LinkList)malloc(sizeof(LNode)); //生成新结点
s->data=e;
s->next=p->next;
p->next=s;
return OK;
}

Status ListSwap_L(LinkList &L,int pos){
//将单链表中第pos个结点和其前驱结点的相应逻辑顺序进行交换
if(pos<=1 || pos>len) return ERROR;//pos小于等于1或者大于表长
LinkList p=L;
int j=0;
while(p && j<pos-2)
{
p=p->next;
++j;
} //选找pos位置的前驱的前驱
LinkList q=p->next;//将pos位置的前驱结点赋值给q
LinkList s=q->next;//将pos位置的结点赋值给s
p->next=s;
q->next=s->next;
s->next=q;
return OK;
}

Status ListChoise_L(LinkList &L) {
LinkList p,q,s;
int temp;
for(p=L;p;p=p->next)
{
s=p; /*给记号赋值*/
for(q=p->next;q;q=q->next)
if(s->data>q->data) s=q; /*是k总是指向最小元素*/
if(p!=s)
{ /*当k!=i是才交换，否则i即为最小*/
temp=p->data;
p->data=s->data;
s->data=temp;
}
}
return OK;
}

void Display_L(LinkList L) {
//对单链表进行输出
LinkList head;
head=L;
L=L->next;
printf("\nThe list is:");
while(L)
{
printf("%d ",L->data);
L=L->next;
}
L=head;
}

Status ListDelete_L(LinkList &L,int i,ElemType &e){
//在带头结点的单链表L中，删除第i个元素，并由e返回值
LinkList p=L;
int j=0;
while(p->next && j<i-1){
p=p->next;
j++;
}//选找第i个结点，并令p指向其前驱
if(!(p->next) || j>i-1) return ERROR;//删除位置不合理
struct LNode *q=p->next;
p->next=q->next;
e=q->data;
free(q);
return OK;
}

main()
{
int x,y,a,b,pos;
LinkList L;

CreatList_L(L);
Display_L(L);

printf("\nInput where to insert:");
scanf("%d",&x);
printf("\nInput the num to insert:");
scanf("%d",&a);
ListInsert_L(L,x,a);
Display_L(L);

printf("\nInput where to delete:");
scanf("%d",&y);
ListDelete_L(L,y,b);
printf("\nPut out the list:");
Display_L(L);
printf("\nThe delete num is:");
printf(" %d ",b);

printf("\nThe pos is:");
scanf("%d",&pos);
ListSwap_L(L,pos);
printf("\nPut out the list:");
Display_L(L);

ListChoise_L(L);
printf("\nAfter choise the list is:");
Display_L(L);

printf("\n");
return OK;

}