算法(顺序表逆置 单链表逆置)_顺序表逆置算法链表逆置算法对比

顺序表逆置
两两交换分别是首尾交换一次和中间两个数交换一次 所以这种逆置方法的交换次数是总长度的一半n/2;

void nizhi(sqlist *L)
{
 int i,t;
 for(i = 0;i <= L->length-3;i++)
 {
  t = L->data[i];
  L->data[i]   =L->data[L->length-1-i];
  L->data[L->length-i-1] = t;  
 }
 for(i = 0;i<=L->length-1;i++)
 {
  printf("%d\n",L->data[i]);
 } 
} 
int main()
{
 sqlist L={{1,2,3,4},4};
 printf("进行逆置\n");
 nizhi(&L); 
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

单链表逆置
1先定义一个p 指向 头结点的指针域
2将头结点的指针域 赋值为NULL 表示头指针与后边的链表开始断开
3进入循环 p相当于一个移动靶的指针 定义一个q为当前靶的指针 用q来进行操作
4进行头插的方法

void nizhi(NODE headnode)
{
 NODE q,p;
 p = headnode->next;//定义移动靶指针
 headnode->next = NULL;//断开链表
 while(p != NULL)
 {
  q = p;
  p = p->next;//移动靶指针
  
  q->next = headnode->next;//头插
  headnode->next = q;
 } 
}
1
2
3
4
5
6
7
8
9
10
11
12
13

完整代码

typedef struct node
{
 struct node *next;
 int data;
}lnode,*NODE;

NODE createlist()
{
 NODE headnode = (NODE)malloc(sizeof(lnode));
 headnode->next = NULL;
 return headnode;
} 


void backinsert(NODE headnode)
{
 NODE p =  headnode;
  int x; 
  printf("请输入\n");
  scanf("%d",&x);
   while(x != 0)
   {
    p->next = (NODE)malloc(sizeof(lnode));
    p = p->next;
    p->data =  x;
    scanf("%d",&x); 
   }
   p->next = NULL; 
}



void nizhi(NODE headnode)




void print(NODE headnode)
{
 NODE pmove = headnode->next;
  while(pmove != NULL)
  {
   printf("%d",pmove->data);
   pmove = pmove->next; 
  } 
 } 
int main()
{
 NODE headnode = createlist();
 printf("即将进行逆置\n");
 backinsert(headnode);//尾插建立链表
 nizhi(headnode);
 print(headnode); 
 } 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53