顺序表
#include<iostream>
using namespace std;
//动态数组实现顺序表
struct List
{
int *arr;
int lenth;
};
//创建顺序表
List createList()
{
List list;
list.lenth=0;
list.arr=new int[100];
return list;
}
//插入操作
void insert(List& list,int pos,int val)
{
if(list.lenth==100)
{
cout<<"顺序表已满,插入失败!"<<endl;
return;
}
for(int i=list.lenth-1;i>=pos;i--)
list.arr[i+1]=list.arr[i];
list.arr[pos]=val;
list.lenth++;
}
//查找操作
int find(List list,int val)
{
for(int i=0;i<list.lenth;i++)
{
if(list.arr[i]==val)
return i;
}
return -1;
}
//输出操作
void print(List list)
{
for(int i=0;i<list.lenth;i++)
cout<<list.arr[i]<<" ";
cout<<endl;
}
int main()
{
List list=createList();
insert(list, 0, 1);//pos=0是插入第一个位置
insert(list, 1, 2);
print(list);
int index = find(list, 2);
cout << index << endl;
return 0;
}
单链表
#include<iostream>
using namespace std;
//节点定义
struct Node
{
int val;
Node* next;
Node(int x):val(x),next(NULL){};
};
//头插法创建单链表
Node* CreateListByHead(int a[],int n)
{
Node* head=NULL;
for(int i=0;i<n;i++)
{
Node* node=new Node(a[i]);
if(head==NULL)
head=node;
else
{
node->next=head;
head=node;
}
}
return head;
}
//带虚拟头结点 头插法创建单链表
Node* CreateListWithHead(int a[],int n)
{
Node* dummy=new Node(-1);
for(int i=0;i<n;i++)
{
Node* node=new Node(a[i]);
node->next=dummy->next;
dummy->next=node;
}
return dummy->next;
}
//尾插法建立单链表
Node* CreateListByTail(int a[],int n)
{
Node* head=NULL;
Node* tail=NULL;
for(int i=0;i<n;i++)
{
Node* node=new Node(a[i]);
if(head==NULL)
{
head=node;
tail=node;
}
else
{
node->next=tail->next;
tail->next=node;
}
}
return head;
}
//带虚拟头结点 尾插法建立单链表
Node* CreateListWithTail(int a[],int n)
{
Node* dummy=new Node(-1);
Node* tail=dummy;
for(int i=0;i<n;i++)
{
Node* node=new Node(a[i]);
node->next=tail->next;
tail=node;
}
return dummy->next;
}
//按序号查找结点
Node *GetNodeByIndex(Node* head,int i)
{
Node* p=head;
while(i--)p=p->next;
return p;
}
//按值查找结点
Node *GetNodeByVal(Node* head,int e)
{
for(Node* p=head;p;p=p->next)
{
if(p->val==e)
return p;
}
return NULL;
}
//在下表为index的位置上插入值为x的新节点
void insertNode(Node* head, int index, int x)
{
if(index==0)
{
auto p=new Node(x);
p->next=head;
head=p;
return;
}
Node *p = head;
for (int i = 0; i < index - 1; i ++)
p = p->next;
Node *newNode = new Node(x);
newNode->next = p->next;
p->next = newNode;
}
//删除链表下标为index的节点
void deleteNode(Node* head, int index)
{
if(index==0)
{
head=head->next;
return;
}
Node *p = head;
for (int i = 0; i < index - 1; i ++)
p=p->next;
p->next=p->next->next;
}
// 遍历链表
void print(Node *head)
{
for (Node *p = head; p; p = p->next)
cout<<p->val<<" ";
cout<<endl;
}
int main()
{
int a[] = {1, 5, 6, 2, 9, 2};
int n = sizeof(a) / sizeof(int);
Node *head = CreateListByTail(a, n);
print(head);
insertNode(head, 2, 0);
print(head);
deleteNode(head, 2);
print(head);
return 0;
}
静态链表
const int N = 10010;
struct Node
{
int val;
int next;
} q[N];