一、線性表
雙連結清單删除元素
删除元素和 增加元素的大忌就是導緻引用連斷鍊
s->next = p->next;
s->prior = p;
p->next = s;
s->next->prior = s;
雙連結清單删除元素
s->prior->next = s->next;
s->next->prior = s-prior;
free(s);//記住删除元素後要釋放這個元素
靜态連結清單節點類型定義
靜态連結清單可以了解為數組
typedef struct{
int data;
int next;
}SLNode;
順序表的插入删除
//建表
int sqList[maxSize] = {1,2,3,...,n}
int length = n;
/* sqList是待插入的數組，length是數組大小，因為需要改變大小，是以這裡是引用類型
* p表示往哪裡插，也就是位置，e表示元素
*/
int insertElem(int sqList[],int &length,int p,int e){
if(p<0||p>length){
return 0;//插入位置不合理
}
//元素分别後移
for(int i = length-1;i>p;--i){
sqList[i+1] = sqList[i]
}
//插入資料，長度+1
sqList[p] = e;
++length;
return 1;//傳回1表示插入成功
}
//與插入不同的參數是e,一般要拿到删除元素的值，是以需要引用值
int deleteElem(int sqList,int &length,int p;int &e){
if(p<0||p>length-1){
return 0;
}
e = sqList[p];
for(int i=p;i<length-1;++i){
sqList[i] = sqList[i+1];
}
--length;
return 1;
}
//尾插法
void createLinkListR(LNode *&head){
head = (LNode *)malloc(sizeof(LNonde));
head->next = NULL;
LNode *p = NULL,*r = head;
int n;
std::cin>>n;//scanf("%d",&a)
for(int i=0;i<n;++i){
std::cin>>p->data;//scanf("%d",&(p->data));
p->next = r->next;
r->next = p;
r = p;
}
}
//頭插法
void createLinkListH(LNode *&head){
head = (LNode *)malloc(sizeof(LNode));
head->next = NULL;
LNode *p = NULL;
int n;
std::cin>>n;//scanf("%d",&n);
for(int i=0;i<n;i++){
p = (LNode *)malloc(sizeof(LNode));
p->next = NULL;
std::cin>>p->data;//scanf("%d",&(p->data));
p->next = head->next;
head->next = p;
}
}
鍵盤輸入n個英文字母，輸入格式為 n、C1、C2、…、 Cn,其中n表示字母的個數。請程式設計以這些輸入資料建立一個單連結清單，并要求将字母不重複的存傳入連結表。
void createLinkNoSameElem(LNode *&head){
head = (LNode *)malloc(sizeof(LNode));
head->next = NULL;
LNode *p;
int n;
char ch;
std::cin>>n;
for(int i=0;i<n;i++){
std::cin>>ch;
p = head->next;
while(p!=NULL){
//如果找到一個值，這個值相等，就要跳出循環
if(p->data==ch)
break;
//不相等就繼續周遊
p = p->next;
}
//周遊 如果找到相同的p!=NULL,如果沒找到相同的，那麼p就不為空
if(p==NULL){
p = (LNode *)malloc(sizeof(LNode));
p->data = ch;
p->next = head->next;//這裡說明是頭插法
head->next = p;
}
}
}
逆置問題
- 順序表的逆置
for(int i = left,j = right;i<j;++i,--j){
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
- 連結清單的逆置
while(p->next != q){
t = p->next;
p->next = t->next;
t->next = q->next;
q->next = t;
}
- 真題解答
- 将一段長度為n的數組的前端k(k<n)個元素逆序後移動到數組後段，要求原數組中的元素不丢失；
void reverse(int a[], int left,int right,int k){
int temp;
//當k大于表長的一半，就需要設定i<left-k
for(int i = left,j=right;i<left-k&&i<j;++i,--j){
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
- 将一段長度為n的數組的前端k(k<n)個元素保持原序移動到數組後段，要求原數組中的元素不丢失；
void moveToEnd(int a[],int n,int k){
reverse(a,0,k-1,k);
reverse(a,0,n-1,k);
}
3)，将數組中的元素（X0, X1…Xn-1）,經過移動後變為（Xp，Xp+1,X） void moveP(int a[],int n,int p){
reverse(a,0,p-1,p);
reverse(a,p,p-1,n-p);
reverse(a,0,n-1,n)
}
取最值問題
int max = a[0];
int maxIdx = 0;
for(int i=0;i<n;++i){
if(max<a[i]){
max = a[i];
maxIdex = i;
}
}
//當然取最小值同理，這裡就不寫了
- 連結清單取最值
LNode *p,*q;
int min = head->next->data;
q = p = head->next;
while(p!=NULL){
if(min>p->data){
min = p->data;
q = p;
}
p = p->next;
}
//雙連結清單的最值問題
void maxFirst(DLNode *head){
DLNode *p = head->rlink,*q =p;
int max = p->data;
while(p!=NULL){
if(max<p->data){
max = p->data;
q = p;
}
p = p->rlink;
}
//删除找到的節點
DLNode *l = q->llink;//左節點
*r = q->rlink;//右節點
l->rlink = r;//左節點指向右節點
if(r!=NULL)//雙連結清單，當最後一個節點的值為null的時候，就不需要将右邊指向左邊了
r->llink =l;
//插入操作,也就是插入到頭結點之後
q->llink = head;
q->rlink = head->next;
head->rlink = q;
q->rlink->llink = q;
}
歸并操作(順序表)
void mergearray(int a [],int m,int b[],int n,int c[]){
int i = 0,j = 0;
int k = 0;
while(i<m&&j<n){
if(a[i]<b[j]){
c[k++] = a[i++];//c[k] = a[i];k++;i++;
}else{
c[k++] = b[j++];//c[k] = b[j];k++;j++;
}
}
while(i<m){
c[k++] = a[i++];
}
while(j<n){
c[k++] = b[j++];
}
}
歸并操作（連結清單）
void merge(LNode *A, LNode *B, LNode *&C){
LNode *p = A->next;
LNode *q = B->next;
LNode *r;
C = A ;
C->next = NULL;
free(B);
r = C;
while(p != NULL && q !=NULL){
if(p->data <= q->data){
r->next = p;
r = r->next;
}else{
r->next = q;
r = r->next;
}
}
if(p!=NULL) r->next = p;
if(q!=NULL) r->next = q;
}
//如果是想逆序，倒着插入 就可以了
//歸并操作實作一條逆序序列的代碼
void mergeR(LNode *A, LNode *B,LNode *&C){
LNode *p = A->next;
LNode *q = B->next;
LNode *s;
C = A;
free(B);
while(p!=NULL&&q!=NULL){
if(p->data <= q->data){
s = p;
p = p->next;
s ->next = C->next;
C->next = s;
}else{//p->data >= q->data
s = q;
q = q->next;
s->next = C->next;
C->next = s;
}
}
while(p!=NULL){
s = q;
q = q->next;
s->next = C->next;
C->next = s;
}
while(q!=NULL){
s = p;
p = p->next;
s->next = C->next;
C->next = s;
}
}
劃分
這裡需要提一點就是，線上性表的劃分當中經常會出現樞軸這類的問題，也就是誰在樞軸的坐标都是小于樞軸的，樞軸的右邊都是大于數軸的，但是具體得看題目怎麼說了
void partition(int arr[], int n){
int temp;
int i = 0;
int j = n-1;
while(i<j){
while(i<j&&arr[j]>==temp) --j;
if(i<j){
arr[i] = arr[j];
++i;
}
while(i<j&&arr[i]<temp) --i;
if(i<j){
arr[j] = arr[i];
--j;
}
}
arr[i] = temp;
}
![【資料結構】 醫院選址[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)