C \ # 데이터 구조 와 알고리즘
23562 단어 C\#기초
기본 개념
데이터 구조:
데이터 구 조 는 서로 한 가지 또는 여러 가지 특정한 관계 가 존재 하 는 데이터 요소 의 집합 이다.그 어떠한 문제 에서 도 데이터 요소 간 에 고립 된 것 이 아니 라 일정한 관계 가 존재 한다. 이런 관 계 를 구조 라 고 하 는데 데이터 요소 간 의 관계 의 서로 다른 특성 에 따라 보통 4 가지 기본 데이터 구조 가 있다.
4. 567917. 집합 구조: 이 구조 중의 데이터 요 소 는 '같은 집합 에 속 하 는' 관 계 를 제외 하고 그 어떠한 관계 도 존재 하지 않 는 다.배열 이 라 든 가 집합 이 라 든 가.
4. 567917. 선형 구조: 이 구조 중의 데이터 요 소 는 일대일 의 관계 가 존재 하고 서로 직렬 로 연결된다
4. 567917. 나무 구조: 이 구조 중의 데이터 요 소 는 한 쌍 의 다 중 관계 가 존재 하고 서로 나무 모양 으로 연결된다
4. 567917. 도형 구조: 이 구조 중의 데이터 요 소 는 여러 쌍 의 관계 가 존재 하고 서로 그림 모양 으로 연결된다
알고리즘:
알고리즘 은 기본 연산 과 규정된 연산 순서 로 구 성 된 완전한 문 제 를 해결 하 는 절차 로 이해 할 수 있다.또는 요구 에 따라 설 계 된 유한 하고 정확 한 계산 서열 이 라 고 할 수 있 으 며 이런 절차 와 서열 은 문 제 를 해결 할 수 있다.
알고리즘 과 데이터 구조의 관계
데이터 구 조 는 데이터 가 프로그램 에 저장 되 는 구조 와 기본 데이터 조작 이 라 고 볼 수 있다.
알고리즘 은 데이터 구 조 를 바탕 으로 문 제 를 해결 하 는 것 이 라 고 볼 수 있 고 알고리즘 은 데이터 구 조 를 바탕 으로 한다.
데이터 구 조 는 문제 의 핵심 이 고 알고리즘 의 기초 이다.
알고리즘 평가 기준
1. 운행 시간.실행 시작 부터 실행 완료 까지 걸 리 는 시간 입 니 다.
2. 차지 하 는 공간.즉, 알고리즘 이 실행 되 는 동안 사용 하 는 최대 메모리 공간 입 니 다.
3. 알고리즘 의 정확성, 가 독성, 건장 성.
운행 시간 이 짧 을 수록 점용 공간 이 적 고 가 독성 이 높 으 며 건장 성 이 좋 으 며 알고리즘 논리 가 비교적 좋다 는 것 을 설명 한다.그러나 때때로 우 리 는 공간 을 희생 해서 시간 을 바 꾸 거나 시간 을 희생 해서 공간 을 바 꿔 야 한다.현대 컴퓨터 의 발전 에 따라 메모리 가 점점 커지 기 때문에 우 리 는 운행 시간 에 더욱 편중 된다.실제 프로젝트 에서 프로젝트 수요 에 따라 가장 좋 은 비례 를 찾 는 것 이 가장 좋 은 해결 방안 이다.
데이터 구조
1. 선형 구조
선형 구 조 는 가장 간단 하고 기본 적 이 며 가장 자주 사용 하 는 데이터 구조 이다.선형 구조의 특징 은 구조 중의 데이터 요소 간 에 일대일 의 선형 관계 가 존재 한 다 는 것 이다.이러한 일대일 관 계 는 데이터 요소 간 의 위치 관 계 를 말 하 는데 선형 구조 데이터 위 치 는 선후 관 계 를 가지 고 하나씩 배열 한 데이터 구 조 는 줄 을 서 는 것 과 유사 하 다.
순서 표:
순서 표 는 선형 구조 중의 데이터 구조 방식 이다.
장점: 순서 표 는 논리 적 으로 인접 한 데이터 요소 가 메모리 에 있 는 위치 도 인접 하기 때문에 순서 표를 찾 을 때 매우 편리 하 다.
단점: 마찬가지 로 순서 표 데이터 요소 가 물리 적 메모리 위치 에 인접 한 요소 로 인해 데 이 터 를 삽입 하고 삭제 할 때 다른 데 이 터 를 이동 해 야 합 니 다. 효율 저 하 를 초래 하 다.
C \ # 에서 List < > 는 하나의 선형 표 입 니 다. 아래 에 우 리 는 간단 한 선형 표 MyList 를 실현 합 니 다. 코드 를 전달 하 는 데 편리 하도록 인터페이스 와 종 류 를 같은 스 크 립 트 에 두 었 습 니 다. 이것 은 규범 에 부합 되 지 않 는 것 같 습 니 다.?
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace
{
///
/// List ，
/// List
/// 1 ，
/// ， ，
///
class MyList : MyListInterface
{
private T[] myDatas;
private int capacity = 0;//
private int CurrentCapacity = -1;//
public MyList()
{
myDatas = new T[] { };
}
///
/// ，
///
public T this[int index] => GetElem(index);
///
/// List
///
public int Length => GetLength();
///
/// MyList
///
public void Add(T item)
{
// , ， ，
// ， +1
T[] temp = myDatas;
myDatas = new T[++capacity];
if (CurrentCapacity == -1)
myDatas[++CurrentCapacity] = item;
else
{
for (int i = 0; i < temp.Length; i++)
{
myDatas[i] = temp[i];
}
myDatas[++CurrentCapacity] = item;
}
}
///
///
///
public void Clear()
{
myDatas = new T[] { };
CurrentCapacity = -1;
capacity = 0;
}
///
///
///
public void Delete(int index)
{
T[] temp = new T[Length - 1];
int tempNum = 0;
for (int i = 0; i < Length - 1; i++)
{
if (index == i)
{
tempNum = 1;
temp[i] = myDatas[i + tempNum];
}
else
{
temp[i] = myDatas[i+ tempNum];
}
}
myDatas = temp;
//
CurrentCapacity--;
capacity--;
}
///
///
///
public T GetElem(int i)
{
return myDatas[i];
}
///
///
///
public void Insert(T item, int index)
{
T[] temp = myDatas;
myDatas = new T[++capacity];
int tempNum = 0;
for (int i = 0; i < Length; i++)
{
if (index == i)
{
myDatas[i] = item;
tempNum = 1;
}
else
myDatas[i] = temp[i - tempNum];
}
}
///
/// MyList Null
///
public bool IsEmpty()
{
return myDatas.Length == 0;
}
///
///
///
public int Locate(T value)
{
for (int i = 0; i < myDatas.Length; i++)
{
if (myDatas[i].Equals(value))
return i;
}
return -1;
}
///
///
///
public int GetLength()
{
return myDatas.Length;
}
}
public interface MyListInterface
{
int Length { get; } //
void Clear(); //
bool IsEmpty(); // null
void Add(T item); //
void Insert(T item, int i); //
void Delete(int i); //
T GetElem(int i); //
T this[int index] { get; } //
int Locate(T value); //
}
}
단일 체인 테이블:
단일 체인 표 도 선형 구조 중의 데이터 구조 방식 이다.
장점: 링크 는 논리 적 으로 인접 한 데 이 터 를 물리 적 메모리 에 도 인접 하도록 요구 하지 않 고 물리 적 메모리 의 파편 공간 을 잘 이용 하기 때문에 링크 의 삽입 과 삭제 등 작업 을 합 니 다. 이동 데이터 가 필요 없 이 운행 속 도 를 높 였 다.
단점: 순서 표 처럼 데 이 터 를 빠르게 읽 을 수 없습니다.
4. 567917. 단 방향 링크: 노드 는 인접 한 다음 노드 의 정 보 를 포함 하고 단 방향 으로 만 조회 할 수 있 으 며 단 방향 링크 라 고 부른다
4. 567917. 양 방향 링크: 노드 는 서로 인접 한 상하 두 노드 를 포함 하고 특정한 노드 에서 양 방향 으로 조작 할 수 있 으 며 양 방향 링크 라 고 부른다
4. 567917. 순환 링크: 링크 의 끝 노드 와 머리 노드 가 연결 되 고 끝 노드 를 조회 할 때 머리 노드 를 되 돌려 주 고 순환 작업 을 할 수 있 으 며 순환 링크 라 고 부른다
4. 567917. 링크 의 조작 방식 은 대동소이 하고 프로젝트 에서 그런 구 조 를 사용 해 야 하 며 프로젝트 의 수요 에 따라 결정 해 야 한다
4. 567917. c \ # 에서 LinkedList 류 를 제공 하여 기본 데이터 요 소 를 조작 하 는데 이것 은 양 방향 링크 입 니 다
단일 체인 테이블 의 간단 한 실현 방식:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace
{
class MyLinkList : MyListInterface
{
private Node headNode;// ， 、 、
private Node endNode;// ， ，
private int length = 0;
public MyLinkList()
{
headNode = null;
endNode = null;
}
public T this[int index] => GetElem(index);
public int Length => length;
///
///
///
public void Add(T item)
{
Node node = new Node(item);// ，
if (headNode == null)
{
headNode = node;
}
else if (headNode != null && endNode == null)
{
endNode = node;
headNode.NextNode = endNode;
}
else
{
endNode.NextNode = node;
endNode = node;
}
length++;
}
///
/// null， GC
///
public void Clear()
{
length = 0;
headNode = null;
endNode = null;
}
///
///
///
public void Delete(int index)
{
if (index >= Length || index < 0)
return;
Node temp = null;
if (index == Length-1) //
{
length--;
for (int i = 0; i < Length; i++)
{
temp = temp == null ? headNode : temp.NextNode;//
}
temp.NextNode = null;
endNode = temp;
}
else if (index == 0)//
{
length--;
headNode = headNode.NextNode;
}
else
{
Node beforeTheNode = null; //
for (int i = 0; i < index; i++)
{
beforeTheNode = beforeTheNode == null ? headNode : beforeTheNode.NextNode;//
}
beforeTheNode.NextNode = beforeTheNode.NextNode.NextNode;//
}
}
///
///
///
public T GetElem(int index)
{
Node temp = null;
for (int i = 0; i <= index; i++)
{
temp = temp == null ? headNode : temp.NextNode;
}
return temp != null ? temp.Data : default(T);
}
///
///
///
public void Insert(T item, int index)
{
if (index > Length|| index<0)
return;
else if (index == Length)// ， Add
Add(item);
else if(index==0)//
{
length++;
Node value = new Node(item);
value.NextNode = headNode;
headNode = value;
}
else
{
length++;
Node value = new Node(item);
Node beforeTheNode = null; //
Node afterTheNode = null; //
for (int i = 0; i < index; i++)
{
beforeTheNode = beforeTheNode == null ? headNode : beforeTheNode.NextNode;//
}
afterTheNode = beforeTheNode.NextNode;//
beforeTheNode.NextNode = value; //
value.NextNode = afterTheNode; //
}
}
///
///
///
public bool IsEmpty()
{
return headNode == null ? true : false;
}
///
///
///
public int Locate(T value)
{
int index = -1;
Node temp = null;
for (int i = 0; i < Length; i++)
{
temp = temp == null ? headNode: temp.NextNode;
if (temp != null && temp.Data.Equals(value))
{
index = i;
break;
}
else if (temp==null)
return -1;
}
return index;
}
public override string ToString()
{
string Info = string.Empty;
for (int i = 0; i < Length; i++)
{
Info += " " + GetElem(i);
}
return Info;
}
}
public interface MyListInterface
{
///
///
///
int Length { get; }
///
///
///
void Clear();
///
/// null
///
bool IsEmpty();
///
///
///
void Add(T item);
///
///
///
void Insert(T item, int i);
///
///
///
void Delete(int i);
///
///
///
T GetElem(int i);
///
///
///
T this[int index] { get; }
///
///
///
int Locate(T value);
}
}
창고.
스 택 과 대기 열 은 두 가지 매우 중요 한 데이터 구조 로 소프트웨어 디자인 에서 많이 응용 된다.스 택 과 대기 열 도 선형 구조 로 선형 표, 스 택, 대기 열 등 세 가지 데이터 구조의 데이터 요소 와 데이터 요소 간 의 논리 적 관 계 는 완전히 같 고 차 이 는 스 택 과 대기 열 이 하나의 규칙 에 의 해 제약 되 는 것 이다.
4. 567917. 스 택: 먼저 들 어간 후에 나 오고 먼저 저금 한 것 은 마지막 에 꺼 낼 수 있 습 니 다. 마치 돈 을 상자 에 넣 고 마지막 에 넣 은 것 을 가장 먼저 꺼 내 는 것 과 같 습 니 다. 똑 같이 가장 먼저 넣 은 것 을 마지막 에 꺼 내기 때문에 스 택 에 관 한 작업 은 모두 표 끝 (스 택 꼭대기) 에서 진행 되 고 다른 한 끝 은 움 직 일 수 없 는 것 을 스 택 밑 이 라 고 합 니 다
4. 567917. 대기 열: 먼저 들 어가 서 먼저 나 오고 먼저 저장 한 것 이 먼저 나 오 며 줄 을 서 는 것 과 유사 합 니 다
C \ # 에서 일반적인 Stack 클래스 를 제공 합 니 다: 일반적인 방법 포함
Stack stack = new Stack();
stack.Push("555"); //
stack.Push("888");
stack.Push("888");
stack.Push("777");
var value = stack.Pop(); // ， ，
value = stack.Peek(); // ， （ ）
int count = stack.Count;//
stack.Contains("555"); //
stack.Clear(); // 우 리 는 스스로 배열 을 통 해 간단 한 스 택 을 실현 합 니 다.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace
{
///
/// ： ( )，
///
class MyStock : MyStockInterface
{
private T[] datas;
public int Count => datas.Length;
public MyStock()
{
datas = new T[] { };
}
public void Clear()
{
datas = new T[] { };
}
///
///
///
public bool Contains(T value)
{
for (int i = 0; i < datas.Length; i++)
{
if (value.Equals(datas[i]))
{
return true;
}
}
return false;
}
///
/// ，
///
public T Peek()
{
return datas[datas.Length - 1];
}
///
///
///
public T Pop()
{
T[] temp = new T[datas.Length-1];
T value = datas[datas.Length - 1];
for (int i = 0; i < datas.Length-1; i++)
{
temp[i] = datas[i];
}
datas = temp;
return value;
}
///
///
///
public void Push(T value)
{
T[] temp = new T[datas.Length+1];
for (int i = 0; i < temp.Length; i++)
{
if (i == temp.Length - 1)
temp[i] = value;
else
temp[i] = datas[i];
}
datas = temp;
}
}
///
///
///
interface MyStockInterface
{
int Count { get; } //
void Push(T value);//
void Clear(); //
bool Contains(T value); //
T Pop(); //
T Peek(); //
}
}
대열
C \ # 에서 일반적인 Queue 클래스 를 제공 합 니 다: 일반적인 방법 포함
Queue queue = new Queue();
//
queue.Enqueue(" ");
queue.Enqueue(" ");
queue.Enqueue(" ");
queue.Enqueue(" ");
queue.Enqueue(" ");
//
string value = queue.Dequeue();
//
value = queue.Peek();
//
bool isHave = queue.Contains(" ");
//
queue.Clear();
//
int count = queue.Count; 정렬
정렬 은 하나의 집합 이나 서열 을 특정한 데이터 항목 (정렬 항목) 에 따라 증가 하거나 감소 하 는 서열 로 다시 배열 하 는 것 이다.
정렬 근거 로 하 는 데이터 항목 을 정렬 항목 이 라 고 합 니 다.
자주 사용 하 는 정렬 방법: 거품 정렬, 삽입 법 정렬, 선택 법 정렬, 빠 른 정렬 (이분법 정렬)
using System;
namespace
{
class Program
{
static void Main(string[] args)
{
int[] sortInfo = new int[10] { 10,9,5,11,6,5,21,7,8,1 };
MyQueueSort(sortInfo,0, sortInfo.Length-1);
string temp = string.Empty;
foreach (var item in sortInfo)
{
temp += " " + item;
}
Console.WriteLine(temp);
Console.ReadLine();
}
///
/// ：
/// ， ， ， ，
/// new int[10] { , 9,10,7,6,5,4,3,2,1 };
///
static void InsertionSort(int[] datas)
{
for (int i = 1; i < datas.Length; i++)
{
int fiducialData = datas[i];//
bool IsTheMinimum = true;//
// i ， i ， i
for (int j = i-1; j >= 0; j--)
{
//
// ： ， ，
// ： ， ， ， ，
if (datas[j] >= fiducialData)
{
// ， j<0 ， ， fiducialData，
// fiducialData ， fiducialData datas[j] , ，
// bool ：true， else false， ， bool true， ，
//
datas[j + 1] = datas[j];
}
else
{
// ，
// ， bool IsTheMinimum false，
// ， ，
datas[j + 1] = fiducialData;
IsTheMinimum = false;
break;
}
}
if (IsTheMinimum == true)
{
datas[0] = fiducialData;
}
}
}
///
/// ：
/// ，
/// ， ，
///
/// ，
///
static void BubbleSort(int[] datas)
{
for (int i = 0; i < datas.Length; i++)
{
for (int j = i+1; j < datas.Length; j++)
{
if (datas[i] > datas[j])
{
int temp = datas[j];
datas[j] = datas[i];
datas[i] = temp;
}
}
}
}
///
///
/// : ， ，
///
static void SelectionSort(int[] datas)
{
for (int i = 0; i < datas.Length; i++)
{
int mainNum = datas[i]; //
int mainNumIndex = i; //
for (int j = i+1; j < datas.Length; j++)
{
if(mainNum> datas[j])//
{
mainNum = datas[j];//
mainNumIndex = j; //
}
}
//
// i
datas[mainNumIndex] = datas[i];
datas[i] = mainNum;
}
}
///
/// （ ）
///
static void MyQueueSort(int[] values, int left, int right)
{
if (left < right)
{
int median = values[left];// ， ， ， “ ”
int L = left;// ， R
int R = right;// ， L
// ，
while (L < R)
{
// ：
//new int[10] { 5, 8, 9, 6, 4, 10, 1, 2, 3, 7 };
// R==L ， median
while (L < R)
{
if (values[R] < median)
{
// median ， values[R]， median ， “ ” ， values[R] “ ”
values[L] = values[R];
//
// ，
break;
}
else
{
R--;
}
}
// ：
// median ， ,
while (L < R)
{
if (values[L] > median)
{
// median ， values[R] “ ”
values[R] = values[L];
// values[L] ， ， ，
// ， ， L == R
break;
}
else
{
L++;
}
}
}
// ，L==R ==R ==L， L、R ，
// L、R
values[L] = median;
// ， ， ，
// ， 。
// ， left == right ， ， ， ， ，
MyQueueSort(values, left, R - 1);
MyQueueSort(values, L + 1, right);
}
}
}
}
좋은 웹페이지 즐겨찾기
