基本运算的相关算法
建立单链表
算法思路：依次读入表Ｌ=(a0................,an-1)中每一个元素ai（假设为整形），若ai≠结束符（-1）,则为ai创建一节点，然后插入表尾，最后返回链表的头结点指针H.
算法描述：
linklist CreatLinklist()
{
data_t a;
linklist_t h, p, r,
h=(linklist_t(malloc(sizeof(linknode_t))));
r=h;
scanf("%d", &a);
while(a!=-1)
{
p=(linklist_t)malloc(sizeof(linknode_t));
p->data=a;
r->next=p;
r=p;
scanf("%d", &a);
}
r->next=NULL;
return(h);
}
链表查找
-
按序号查找：实现GetLinklist(h, i)运算。
算法思路：从链表的a0起，判断是否为第i结点，若是则返回该结点的指针，否则查找下一结点，依次类推。
算法描述：
linklist_t GetLinklist(linklist_t h, int i)
{
int j = -1;
linklist_t = h;
if(i<0)
return NULL;
while(p->next&&j<i)
{
p = p->next;
j++;
}
if(i==j)
return p;
else
return NULL;
}
-
按值查找（定位）：即实现Locate(h, x)
算法思路：从链表结点a0起，依次判断某结点是否不等于x，若是，则返回该结点的地址，若不是，则查找下一结点a1，以此类推。若表中不存在x,则返回NULL.
算法描述：
linklist Locate(linklist_t h, data_t x)
{
linklist_t p=h->next;
while(p && p->data != x)p=p->next;
return p;
}
链表的插入：即实现InsertLinklist(h, x, i,)。将x插入表中结点ai之前的情况。
算法思路：调用算法GetLinklist(h, i-1),获取结点ai-1的指针p(ai之前驱)，然后申请一个结点，存入x，并将其插入p指向的结点之后。
算法描述：
int InsertLinklist(linklistt h, data_t x, int i)
{
linklist_t p, q;
if(i==0){
p = h;
}
else{
p = GetLinklist(h, i-1);
}
if(p == NULL)
{
return -1;
}
else
{
q = (linklist_t)malloc(sizeof(linknode_t));
q->data = x;
q->next = p->next;
p->next = q;
return 0;
}
}
## 链表的删除
即实现DeleteLinklist(h, i)
算法思路：同插入法，先调用函数GetLinklist(h, i-1),找到结点ai的前驱，将结点删除。
算法描述：
int DeleteLinklist(linklist_t, int i)
{
linklist_t p, q;
if(i==0)
{
p = h;
}
else
{
p = GetLinklist(h, i-1);
}
if(P&&p->next)
{
q = p->next;
p->next = a->next;
free(q);
return 0;
}
else
return -1;
}
## 单链表Ｈ倒置
算法思路：依次取原链表中各结点，将其作为新链表首结点插入H结点之后
算法描述：
void ReverseLinklist(linklist_t h)
{
linklist_t p, q;
p = h->next;
h->next = NULL;
while(p!=NULL)
{
q=p;
p=p->next;
q->next=h->next;
h->next=q;
}
}
## 单链表有序插入
int list_order_insert(linklist H, datatype value)
{
linklist p, q;
if((p =(linklist)malloc(sizeof(listnode))) == NULL){
printf("malloc failed\n");
return -1;
}
p->data = value;
q=H;
while(q->next && q->next->data <value){
q = q->next;
}
p->next = q->next;
q->next =p;
return 0;
}
## 链表排序
void list_sort(linklist H)
{
linklist p, q, r;
p = H->next;
H->next = NULL;
while(p){
q = p;
p = p->next;
r = H;
while(r->next && r->next->data < q->data)
{
r = r->next;
}
q->next = r->next;
r->next = q;
}
}
例题：设ra和rb分别为两循环链表的尾指针，设计算法；实现表ra和rb的简单连接。
P = B->next;
B->next = A->next;
A->next = P->next;
free(P);</pre>
## 双向循环列表
在单链表中，查找ai的后继Next(L, ai),耗时仅为０(1)，因为取ai之后继指针即可。但查找ai的直接前驱Prior(L, ai);则需从链表的头指针开始，找到结点ai前一结点既是。故运算Prior(L, ai)依赖表长n，耗时为0(n)。另外，若链表中有一指针被破坏，则整个链表脱节。这是单链表的不足，为此，引入双向链表。先定义双向链表中的结点：
其中，data和next同单链表，增加一指针域prior,其指向本结点的直接前驱。
结点描述：
typedef int data_t;
typedef struct dnode_t
{
data_t data;
struct dnode_t *prior, *next;
}dlinknode_t, *dlinklist_t;
## 双向循环列表（插入）
插入：即实现在表L的第i结点前插入一结点x的运算
算法思路：调用查找算法Getlist(L, i),获取结点ai的指针p。若p存在，申请一q结点，存入元素x,然后修改指针，将q结点插入p结点之前。
算法描述：
void Dinsert(dlinklist_t L, data_t x, int i)
{
dlinklist_t p, q;
p = Getlist(L, i);
if(p ==NULL)
return;
else
{
q = (dlink)malloc(sizeof(dlinknode));
q->data =x;
q->prior = p->prior;
(p->prior)->next = q;
q->next = p;
p->prior = q;
}
}
int dlist_insert(dlistnode *H, int value, int pos)
{
dlistnode *p, *q;
p = dlist_get(H, pos);
if (p == NULL){
return -1;
}
if((q = (dlistnode *)malloc(sizeof(dlistnode))) == NULL ){
printf("malloc failed\n");
return -1;
}
q->data = value;
q->prior = p->prior;
q->next = p;
p->prior->next = q;
p->prior = q;
return 0;
}
结果：
双向循环链表（删除）
删除：即实现删除链表中第i结点的运算
算法思路：调用查找算法GetLinklist(L, i),获取ai的指针p,若p存在，则修改指针删除之。
算法描述：
void Ddelete(dlinklist_t L, int i)
{
dlink_t p = Getlist(L, i);
if(p == NULL)
{
returnl
}
else
{
(p->prior)->next = p->next;
(p->next)->prior = p->prior;
free(p);
}
}
int dlist_delete(dlistnode *H, int pos){
dlistnode *p;
p = dlist_get(H, pos);
if (p == NULL){
return -1;
}
p->prior->next = p->next;
p->next->prior = p->prior;
free(p);
p = NULL;
return 0;
}
结果：
双线循环链表（查找）
查找：Getlist(L, i)，获取结点ai的指针p
dlistnode *dlist_get(dlistnode *H, int pos)
{
int i = -1;
dlistnode *p = H;
if(pos < 0){
printf("pos < 0, invalid!\n");
return NULL;
}
while(i < pos){
p = p->next;
i++;
if(p == H){
printf("pos is invalid\n");
return NULL;
}
}
return p;
}
结果：
多项式表示与相加
typedef struct{
float coef;
int exp;
}data_t;
typedef struct node_t
{
data_t data;
struct node_t *next;
}linknode_t, *linklist_t;
算法思路：
设指针pa,pb分别指向两链表中的某个结点（初始指向第一结点）；
若pa->data. exp < pb->data. exp,则pa结点应为和的第一项；
若pa->data. exp > pb->data. exp,则pb结点应为和的第一项；
若pa->data. exp = pb->data. exp,则两结点对应系数相加；
sum = pa->data. coef + pb->data. coef，若sum≠0, 相加结果应为和的一项。
Joseph问题
算法思路：用一个不带结点的循环链表来处理Josephu问题：先构成一个有n个结点的单循环链表，然后从第k结点起从1计数，计到m时，对应结点从链表中删除；然后再从被删除结点的下一个结点起又从１开始计数......，直到所有节点都出列时算法结束。
void list_jose(linklist H, int k, int m)
{
int i;
linklist r, p;
r = H;
while(r->next->data != k){
r = r->next;
}
printf("k=%d\n", k);
while(r->next != r){
for(i=0;i<m-1;i++){
r = r->next;
}
p = r->next;
r->next = p->next;
printf("%d\n", p->data);
free(p);
p = NULL;
}
printf("%d\n", r->data);
free(r);
r = NULL;
}
结果：
1)如何调节vi编辑器字体的大小?
<Ctrl> + <->减小字号<Ctrl> + <Shift> + <+>增大字号
2）在vi编辑时，有时需要打开另外一个文件，命令是：
:new filename
此刻，出现了上下两个窗口，切换这两个窗口的方法是：ctrl+w，w（先按ctrl+w，再按键w）；
例如在多文件编程时，切换不同的窗口很实用。
采用:vsp命令同时查看多个窗口时，可以用于切换不同窗口。
3）vi 中的撤销操作
'u' : 撤销上一个编辑操作
'ctrl + r' : 恢复，即回退前一个命令
'U' : 行撤销，撤销所有在前一个编辑行上的操作
使用'u '和'CTRL+R' 命令可以恢复到任何编辑过的状态。
4）切换编程窗口
Alt + TAB键
5）在当前目录生成新的Vi窗口
Ctrl + shift +n
如果是在根目录下生成一个窗口：
Ctrl + alt +t
6）、隐藏和折叠代码。
//shift + v选中一行
//上移动移动选择多行
//z + f折叠代码
//z + d打开折叠</pre>
7)、切换输入法
ibus-setup 弹出输入法切换窗口
Ctrl + space 切换输入法
8）、vi中如何跳转到指定行数？
输入｀:n｀，代表跳转到第n行，如｀:79｀，就跳转到第79行。
网友评论